题解 P5157 【[USACO18DEC]The Cow Gathering】

_Fontainebleau_ · 2019-03-12 18:24:46 · 题解

刚学了拓扑排序，A了这道题

#include<iostream>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdlib>
#include<algorithm>
#define N 220000
#define L 200000
#define eps 1e-7
#define inf 1e9+7
#define db double
#define ll long long
#define ldb long double
using namespace std;
inline int read()
{
    char ch=0;
    int x=0,flag=1;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*flag;
}
struct edge{int to,nxt;}e[N*2],E[N*2];
int num,head[N],NUM,HEAD[N];
inline void add(int x,int y){e[++num]=(edge){y,head[x]};head[x]=num;}
inline void ADD(int X,int Y){E[++NUM]=(edge){Y,HEAD[X]};HEAD[X]=NUM;}
queue<int>q;
bool vis[N];
int times,c[N],sz[N],deg[N],deg_[N],dep[N],dfn[N],nxt[N][25];
void dfs(int x,int fa)
{
    sz[x]=1;dfn[x]=++times;dep[x]=dep[fa]+1;
    for(int i=head[x];i!=-1;i=e[i].nxt)
    {
        int to=e[i].to;
        if(to==fa)continue;
        dfs(to,x);sz[x]+=sz[to];nxt[to][0]=x;
    }
}
int get(int x,int k){for(int i=0;i<=20;i++)if(1<<i&k)x=nxt[x][i];return x;}
int main()
{
    num=NUM=-1;memset(head,-1,sizeof(head));memset(HEAD,-1,sizeof(HEAD));
    int n=read(),m=read(),tot=0;
    for(int i=1;i<n;i++){int x=read(),y=read();add(x,y);add(y,x);deg[x]++;deg[y]++;}
    dfs(1,1);
    for(int k=1;k<=20;k++)for(int i=1;i<=n;i++)nxt[i][k]=nxt[nxt[i][k-1]][k-1];
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        ADD(x,y);deg_[y]++;
        int l=dfn[x],r=dfn[x]+sz[x]-1;
        if(l<=dfn[y]&&dfn[y]<=r)
        {
            int to=get(y,dep[y]-dep[x]-1);
            int pl=dfn[to],pr=dfn[to]+sz[to]-1;
            c[pl]--;c[pr+1]++;c[1]++;c[n+1]--;
        }
        else c[l]++,c[r+1]--;
    }
    for(int i=1;i<=n;i++)if(deg[i]==1&&!deg_[i])q.push(i);
    while(!q.empty())
    {
        int x=q.front();q.pop();
        if(vis[x])continue;vis[x]=true;tot++;
        for(int i=head[x];i!=-1;i=e[i].nxt){int to=e[i].to;deg[x]--;deg[to]--;}
        for(int i=HEAD[x];i!=-1;i=E[i].nxt){int to=E[i].to;deg_[to]--;}
        for(int i=head[x];i!=-1;i=e[i].nxt){int to=e[i].to;if(deg[to]==1&&!deg_[to])q.push(to);}
        for(int i=HEAD[x];i!=-1;i=E[i].nxt){int to=E[i].to;if(deg[to]==1&&!deg_[to])q.push(to);}
    }
    if(tot<n){for(int i=1;i<=n;i++)printf("0\n");return 0;}
    for(int i=1;i<=n;i++)c[i]+=c[i-1];
    for(int i=1;i<=n;i++)printf("%d\n",c[dfn[i]]?0:1);
    return 0;
}