洛谷 P1653 == COGS 2043 猴子

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

 //由于无法评测 ~~

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 #define maxn 200010

 #define maxm 400010

 const int INF=1e9;

 int n,m,son[][maxn],fa[maxn],ans[maxn];

 struct fy{

     int id,son;

 } pr[maxm];

 bool mark[][maxn];

 inline void readin(int &d)

 {

     char t=getchar();bool markk=false;

     while(t<''||t>'') {if(t=='-') markk=true;t=getchar();}

     for(d=;!(t<''||t>'');t=getchar()) d=(d<<)+(d<<)+t-'';

     if(markk) d=-d;

 }

 int find(int x){// 并查集查询祖先的过程当中 处理一下

     // 取 它放手最早的 祖先

     if(fa[x]==x) return x;

     int temp=find(fa[x]);

     ans[x]=min(ans[x],ans[fa[x]]);

     return fa[x]=temp;

 }

 void Get_fa(int u,int v,int val){

     int rx=find(u),ry=find(v);

     if(rx!=ry){

         if(rx==) { fa[ry]=rx,ans[ry]=val; }

         else { fa[rx]=ry,ans[rx]=val; }

     }

 }

 int main()

 {

     freopen("monkeya.in","r",stdin);

     freopen("monkeya.out","w",stdout);

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++){

         readin(son[][i]);readin(son[][i]);

         fa[i]=i;ans[i]=INF;

     }

     for(int i=;i<=m;i++){

         readin(pr[i].id),readin(pr[i].son);

         mark[pr[i].son][pr[i].id]=true;

         //表示联通性

     }

     for(int i=;i<=n;i++){

         if(!mark[][i]&&son[][i]!=-)

           Get_fa(i,son[][i],m);

         if(!mark[][i]&&son[][i]!=-)

           Get_fa(i,son[][i],m);

     }

     for(int i=;i<=n;i++)

       if(find(i)==) ans[i]=INF;

     // 此处 从后向前处理

     for(int i=m;i>=;i--){

         if(son[pr[i].son][pr[i].id]!=-)

           Get_fa(pr[i].id,son[pr[i].son][pr[i].id],i-);

     }

     for(int i=;i<=n;i++)

       find(i),printf("%d\n",(ans[i]==INF ? - : ans[i]));

     return ;

 }

 // 对于各个点都用并查集维护  她掉落的时间由他的所有的

 // 祖先中 松手最早的那一只 猴子 决定

巴特西

洛谷 P1653 == COGS 2043 猴子

输入格式

输出格式

样例输入

样例输出

提示

最新文章

热门文章