为什么第7个点一直TLE

P3806 【模板】点分治 1

银翼的魔术师 @ 2020-07-21 17:40:32

本不想发帖的,但一直过不了且不知道是被卡常还是哪里写错了,非常难受。

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<utility>
#include<bitset>
#include<cstdio>
#include<string>
#include<time.h>
#include<vector>
#include<cmath>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
const int N=1e4+5,M=1e7+5;
int f[N],ne[N<<1],t[N<<1],q[N<<1],b,s[N],r,rs,d[N],k,nm;
bool bk[M],v[N];
int read()
{
    int x=0;
    char c;
    do
        c=getchar();
    while(c>'9'||c<'0');
    while(c<='9'&&c>='0')
    {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x;
}
void add(int u,int v,int w)
{
    ne[++b]=f[u];
    f[u]=b;
    t[b]=v;
    q[b]=w;
}
void num(int x,int fa)
{
    nm++;
    for(int i=f[x];i;i=ne[i])
        if(fa!=t[i]&&!v[t[i]])
            num(t[i],x);
}
void zx(int x,int fa)
{
    int mxs=0;
    s[x]=1;
    for(int i=f[x];i;i=ne[i])
        if(fa!=t[i]&&!v[t[i]])
        {
            zx(t[i],x);
            s[x]+=s[t[i]];
            mxs=max(mxs,s[t[i]]);
        }
    mxs=max(mxs,nm-s[x]);
    if(mxs<rs||!r)
    {
        r=x;
        rs=mxs;
    }
}
bool dfs(int x,int fa)
{
    if(d[x]>k)
        return 0;
    else
        if(bk[k-d[x]])
            return 1;
    for(int i=f[x];i;i=ne[i])
        if(t[i]!=fa&&!v[t[i]])
        {
            d[t[i]]=d[x]+q[i];
            if(dfs(t[i],x))
                return 1;
        }
    return 0;
}
void last(int x,int fa)
{
    if(d[x]>k)
        return;
    bk[d[x]]=1;
    for(int i=f[x];i;i=ne[i])
        if(t[i]!=fa&&!v[t[i]])
            last(t[i],x);
}
void pre(int x,int fa)
{
    if(d[x]>k)
        return;
    bk[d[x]]=0;
    for(int i=f[x];i;i=ne[i])
        if(t[i]!=fa&&!v[t[i]])
            pre(t[i],x);
}
bool df(int x)
{
    nm=r=0;
    num(x,0);
    zx(x,0);
    d[r]=0;
    bk[0]=1;
    for(int i=f[r];i;i=ne[i])
        if(!v[t[i]])
        {
            d[t[i]]=q[i];
            if(dfs(t[i],r))
            {
                for(int j=f[r];j;j=ne[j])
                    if(!v[t[j]])
                    {
                        if(t[j]==t[i])
                            break;
                        pre(t[j],r);
                    }
                return 1;
            }
            last(t[i],r);
        }
    pre(r,0);
    v[r]=1;
    for(int i=f[r];i;i=ne[i])
        if(!v[t[i]])
            if(df(t[i]))
                return 1;
    return 0;
}
int main()
{
    int n,m,u,vv,w;
    n=read(),m=read();
    for(int i=1;i<n;i++)
    {
        u=read(),vv=read(),w=read();
        add(u,vv,w);
        add(vv,u,w);
    }
    for(int i=1;i<=m;i++)
    {
        memset(v,0,sizeof(v));
        k=read();
        if(df(1))
            printf("AYE\n");
        else
            printf("NAY\n");
    }
}

by 鏡音リン @ 2020-07-21 18:04:29

卡常了吧


by zhoukangyang @ 2020-07-21 18:26:49

建议把操作存下来,离线处理,这题不卡常的qwq


by 银翼的魔术师 @ 2020-07-21 20:28:57

好吧,谢谢,已经过了。这题深刻告诉我们做淀粉质要离线,在线TLE,离线直接跑出最优解。


by 银翼的魔术师 @ 2020-07-21 20:29:49

淀粉质真的常熟巨大


|