wa40求助
查看原帖
wa40求助
289304
HAuCl4楼主2022/11/19 10:41
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1000000007,N=66666,M=233333;
int n;
int seq[N],deg[N];
int sz[M];
namespace G0{
    int hd[N],to[M],nxt[M],tot;
    void add(int x,int y)
    {
        to[++tot]=y;
        nxt[tot]=hd[x];
        hd[x]=tot;
    }
}
namespace G1{
    int hd[N],to[M],nxt[M],tot;
    void add(int x,int y)
    {
        to[++tot]=y;
        nxt[tot]=hd[x];
        hd[x]=tot;
    }
}
namespace G2{
    int hd[M],to[M],nxt[M],tot;
    void add(int x,int y)
    {
        to[++tot]=y;
        nxt[tot]=hd[x];
        hd[x]=tot;
    }
}
 
 
int dep[N],fa[N];
int anc[N][20];
int lca(int x,int y)
{
//  if(dep[x]==0 || dep[y]==0) return -1;
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=17;i>=0;i--)
    {
        if(anc[i][x]!=0&&dep[anc[i][x]]>=dep[y])
        x=anc[i][x];
    }
    if(x==y) return x;
    for(int i=17;i>=0;i--)
    {
        if(anc[i][x]!=0&&anc[i][y]!=0&&anc[i][x]!=anc[i][y])
        {
            x=anc[i][x];
            y=anc[i][y];
        }
    }
    return anc[0][x];
}
void init(int x)
{
    anc[0][x]=fa[x];
    for(int i=1;i<=17;i++) anc[i][x]=anc[i-1][anc[i-1][x]];
}
void make_tree()
{
    using namespace G1;
//  dep[0]=1;
//  fa[0]=anc[0][0]=0;
    dep[n+1]=1;
    fa[n+1]=anc[0][n+1]=n+1;
    init(n+1);
    for(int i=1;i<=n;i++)
    {
        int x=seq[i];
        if(!hd[x])
        {
            fa[x]=n+1;
            G2::add(n+1,x);
//          printf("LINK %d %d\n",n+1,x);
            anc[0][x]=n+1;
            dep[x]=2;
            init(x);
            continue;
        }
        int LCA=to[hd[x]];
        for(int j=hd[x];j;j=nxt[j])
            LCA=lca(LCA,to[j]);
        fa[x]=LCA;
        G2::add(fa[x],x);
//      printf("LINK %d %d\n",fa[x],x);
        dep[x]=dep[fa[x]]+1;
        init(x);
    }
}
void toposort(){
    using namespace G0;
    queue<int> q;
    for(int i=1;i<=n;i++)
        if(!deg[i])
            q.push(i),fa[i]=0;
    int cnt=0;
    while(!q.empty()){
        int u=q.front();q.pop();
//      G2::add(fa[u],u);
//      dep[u]=dep[fa[u]]+1;
//      init(u);
        seq[++cnt]=u;
//      bool ok=0;
        for(int i=hd[u];i;i=nxt[i]){
            int v=to[i];
            deg[v]--;
//          if(fa[v]==-1) fa[v]=u;
//          else fa[v]=lca(fa[v],u);
            if(!deg[v]){
                q.push(v);
//              ok=1;
            }
        }
    }
}
void dfs(int u)
{
    using namespace G2;
//  /*if(u<=n)*/
    sz[u]=1;
    for(int i=hd[u];i;i=nxt[i])
    {
        dfs(to[i]);
        sz[u]+=sz[to[i]];
    }
}
int main()
{
//  freopen("P2597_1.in","r",stdin);
//  freopen("P2597_1.ans","w",stdout);
    memset(deg,0,sizeof(deg));
    scanf("%d",&n);
    memset(anc,0,sizeof(anc));
//  memset(G2::hd,-1,sizeof(G2::hd));
    for(int i=1,ta;i<=n;i++)
    {
        while(scanf("%d",&ta)&&ta)
        {
            G0::add(ta,i);
            G1::add(i,ta);
            deg[i]++;
        }
    }
    toposort();
//  dep[0]=sz[0]=0;
//  for(int i=1;i<=n;i++) printf("%d ",seq[i]); printf("\n");
    make_tree();
    dfs(n+1);
    for(int i=1;i<=n;i++) printf("%d\n",sz[i]-1);
    return 0;
}
2022/11/19 10:41
加载中...