本机AC提交RE

P3806 【模板】点分治 1

sherlock55341 @ 2018-04-04 13:31:40

#include<bits/stdc++.h>
using namespace std;
#define MAXN 10010
#define inf (1<<29)
inline void read(int &x)
{
    int s=0,w=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
    while(isdigit(c))s=(s<<3)+(s<<1)+c-'0',c=getchar();
    x=s*w;
}
int n,m,root,sum,size[MAXN],maxson[MAXN],deep[MAXN],K,temp[MAXN],r;
bool vis[MAXN];
struct edge
{
    int to,nxxt,w;
}e[MAXN<<1];
int head[MAXN],cnt;
inline void add(int x,int y,int z)
{
    e[++cnt].to=y;
    e[cnt].nxxt=head[x];
    e[cnt].w=z;
    head[x]=cnt;
}
void findroot(int u,int fa)
{
    size[u]=1,maxson[u]=0;
    for(register int i=head[u];i;i=e[i].nxxt)
    {
        if(e[i].to==fa||vis[e[i].to])continue ;
        findroot(e[i].to,u);
        size[u]+=size[e[i].to];
        maxson[u]=max(maxson[u],size[e[i].to]);
    }
    maxson[u]=max(maxson[u],sum-size[u]);
    if(maxson[root]>maxson[u])root=u;
}
void find_deep(int u,int fa)
{
    temp[++r]=deep[u];
    for(register int i=head[u];i;i=e[i].nxxt)
    {
        if(e[i].to==fa||vis[e[i].to])continue ;
        deep[e[i].to]=deep[u]+e[i].w;
        find_deep(e[i].to,u);
    }
}
long long cal(int u,int v)
{
    long long ans=0;
    deep[u]=v;
    int l=1;r=0;
    find_deep(u,0);
    sort(temp+1,temp+r+1);
    for(l=1;l<r;l++)
    {
        while(temp[l]+temp[r]>=K)
        {
            if(temp[l]+temp[r]==K)ans++;
            r--;
        }
    }
    return ans;
}
long long ANS;
void solve(int u)
{
    ANS+=cal(u,0);
    vis[u]=true;
    for(register int i=head[u];i;i=e[i].nxxt)
    {
        if(vis[e[i].to])continue ;
        ANS-=cal(e[i].to,e[i].w);
        sum=size[e[i].to];
        root=0,maxson[root]=inf;
        findroot(e[i].to,0);
        solve(root);
    }
}
int main()
{
    read(n),read(m);
    for(register int i=1;i<n;i++)
    {
        int a,b,c;
        read(a),read(b),read(c);
        add(a,b,c),add(b,a,c);
    }
    while(m--)
    {
        memset(vis,0,sizeof(vis));
        root=0,sum=n,maxson[root]=inf;
        ANS=0;
        read(K);
        findroot(1,0);
        solve(root);
        if(ANS)puts("AYE");
        else puts("NAY");
    }
}

如题


by ylxmf2020 @ 2018-04-05 14:07:49

本地AC?您本地如何AC的?


by Rorshach @ 2018-05-12 01:06:05

巧了 我也是啊

数据下来本机能跑过去 但提交就Re


by 人殇物已非 @ 2018-06-12 17:48:26

本地对了就是对了,提交不过是oj的问题


by 人殇物已非 @ 2018-06-12 17:49:24

看看编译原理吧,你访问到了本地的空间,而测评时就RE


|