首页 > 代码库 > NKOI P2107 可爱的猴子

NKOI P2107 可爱的猴子

P2107 可爱的猴子

时间限制:1000MS  空间限制:65535KB

问题描述:

树上有n只猴子。它们编号为 1 到n。1 号猴子用它的尾巴勾着树枝。剩下的猴子都被其他的猴子用手抓着。每只猴子的每只手可以抓住另一只猴子的尾巴。从0 时刻开始,每一秒都有一只猴子松开它的一只手。这会导致一些猴子掉到地上(它们在地上也能继续松开它们的手,猴子落地的时间很短可以不计)。 你的任务是: 写一个程序,从标准输入读入猴子间抓与被抓住的关系信息,和它们放开手的顺 序,对于每一只猴子算出它落地的时间,把结果输出到标准输出。

输入格式

第一行有两个正整数n和m。n是猴子的数量,m是我们观察猴子的时间(单位为秒)。
接下来n行是初始情 况的描述。第k+1 行有两个整数表示第k个猴子抓住的猴子的编号,前一个数 代表左手抓的猴子的编号,后一个数是右手抓的猴子的编号。如果读入的数为-1 则代表猴子的手是空的。
接下来m行是对猴子观察的结果。在这m行里的第i行,有两个整数。前一个是猴子的编号,后一个是它在时刻i−1 时松开的手的编 号(1-左手,2-右手)。

输出格式

输出n个整数,每行一个。第i行表示第i个猴子落地的时间,如果在观察结束前猴子没有落地,那么输出-1

样例输入

3 2
-1 3
3 -1
1 2
1 2
3 1

样例输出

-1
1
1

提示

1≤n≤200000,1≤m≤400000

 

 1 //由于无法评测 ~~  2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 using namespace std; 6 #define maxn 200010 7 #define maxm 400010 8 const int INF=1e9; 9 int n,m,son[3][maxn],fa[maxn],ans[maxn];10 struct fy{11     int id,son;12 } pr[maxm];13 bool mark[3][maxn];14 inline void readin(int &d)15 {16     char t=getchar();bool markk=false;17     while(t<0||t>9) {if(t==-) markk=true;t=getchar();}18     for(d=0;!(t<0||t>9);t=getchar()) d=(d<<1)+(d<<3)+t-0;19     if(markk) d=-d;20 }21 int find(int x){// 并查集查询祖先的过程当中 处理一下 22     // 取 它放手最早的 祖先 23     if(fa[x]==x) return x;24     int temp=find(fa[x]);25     ans[x]=min(ans[x],ans[fa[x]]);26     return fa[x]=temp;27 }28 void Get_fa(int u,int v,int val){29     int f=find(u),s=find(v);30     if(f!=s){31         if(f==1) { fa[s]=f,ans[s]=val; }32         else { fa[f]=s,ans[f]=val; }33     }34 }35 int main()36 {37     scanf("%d%d",&n,&m);38     for(int i=1;i<=n;i++){39         readin(son[1][i]);readin(son[2][i]);40         fa[i]=i;ans[i]=INF;41     }42     for(int i=1;i<=m;i++){43         readin(pr[i].id),readin(pr[i].son);44         mark[pr[i].son][pr[i].id]=true;45         //表示联通性 46     }47     for(int i=1;i<=n;i++){48         if(!mark[1][i]&&son[1][i]!=-1)49           Get_fa(i,son[1][i],m);50         if(!mark[2][i]&&son[2][i]!=-1)51           Get_fa(i,son[2][i],m);52     }53     for(int i=1;i<=n;i++)54       if(find(i)==1) ans[i]=INF;55     // 此处 从后向前处理56     for(int i=m;i>=1;i--){57         if(son[pr[i].son][pr[i].id]!=-1)58           Get_fa(pr[i].id,son[pr[i].son][pr[i].id],i-1);59     }60     for(int i=1;i<=n;i++)61       find(i),printf("%d\n",(ans[i]==INF ? -1 : ans[i]));62     return 0;63 }64 // 对于各个点都用并查集维护  她掉落的时间由他的所有的65 // 祖先中 松手最早的那一只 猴子 决定 

 

NKOI P2107 可爱的猴子