大样例过了小数据wa了

P3806 【模板】点分治 1

尹昱钦 @ 2021-07-25 21:39:44

非常神奇,后四个点过了,前面的全wa了。 蒟蒻求助

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<map>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<bitset>
#include<cstdio>
#include<ctime>
using namespace std;
inline int read()
{
    int f=0;
    char cc=getchar();
    while(cc<'0'||cc>'9')cc=getchar();
    while(cc>='0'&&cc<='9')f=f*10+cc-'0',cc=getchar();
    return f;
}
const int maxn=1e4+5;
const int maxx=1e7;
int n,m,q[maxn],cnt1,cnt,dis[maxn],diss[maxn],rt,p[maxn],mx[maxn],sz[maxn],sum_size,ans[maxn];
bool ext[maxx+5],used[maxn],vis[maxn];
struct node{
    int v,w,next;
}e[maxn*2];
void insert(int u,int v,int w){
    cnt1++;
    e[cnt1].w=w;
    e[cnt1].v=v;
    e[cnt1].next=p[u];
    p[u]=cnt1;
}
void getroot(int u,int fa){
    mx[u]=0;
    sz[u]=1;
    for(int i=p[u];i!=-1;i=e[i].next){
        int v=e[i].v;
        if(vis[v]||v==fa) continue;
        getroot(v,u);
        sz[u]+=sz[v];
        mx[u]=max(mx[u],sz[v]); 
    }
    mx[u]=max(mx[u],sum_size-sz[u]);
    if(mx[u]<mx[rt]) rt=u;
}
void getdis(int u,int fa){
    dis[++cnt]=diss[u];
    for(int i=p[u];i!=-1;i=e[i].next){
        int v=e[i].v;
        if(v==fa||vis[v]) continue;
        diss[v]=diss[u]+e[i].w;
        getdis(v,u);
    }
}
void cal(int u){
    int num=0;
    for(int i=p[u];i!=-1;i=e[i].next){
        int v=e[i].v;
        if(vis[v]) continue;
        cnt=0;
        diss[v]=e[i].w;
        getdis(v,u);
        for(int j=1;j<=cnt;j++){
            for(int k=1;k<=m;k++){
                if(q[k]-dis[j]>=0&&ext[q[k]-dis[j]]) ans[k]=1;
            }
        }
        for(int j=1;j<=cnt;j++){
            if(dis[j]>maxx) continue;
            used[++num]=dis[j];
            ext[dis[j]]=1;
        }
    }
    for(int i=1;i<=num;i++){
        ext[used[i]]=0;
    }
}
void divide(int u){
    vis[u]=ext[0]=1;
    cal(u);
    for(int i=p[u];i!=-1;i=e[i].next){
        int v=e[i].v;
        if(vis[v]) continue;
        mx[rt=0]=sum_size=sz[v];
        getroot(v,0);
        divide(rt);
    }
}
int main(){
    memset(p,-1,sizeof(p));
    n=read();
    m=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        insert(u,v,w);
        insert(v,u,w);
    }
    for(int i=1;i<=m;i++) q[i]=read();
    mx[0]=sum_size=n;
    getroot(1,-1);
    divide(rt);
    for(int i=1;i<=m;i++){
        if(ans[i]==1) printf("AYE\n");
        else printf("NAY\n");
    } 
    return 0;
}

by rfsfreffr @ 2022-08-16 11:57:08

Cu ball


|