1
#include<iostream>
2#include<algorithm>
3#include<vector>
4#include<cmath>
5#include<queue>
6#include<ctime>
7using namespace std;
8
9
10class union_find
{
11
public:
12 union_find(int n=600000);
13
~union_find(){delete []parent;delete []rank;}
14 int Find( int x);
15 int Union(int x,int y);
16 int Virtual(int x);
17private:
18 int *parent;
19 int *rank;
20 int *Root;
21
};
22
23union_find::union_find (int n)
24{
25 parent=new int[n+1];
26 rank=new int[n+1];
27 Root=new int[n+1];
28 for(int i=0;i<=n;i++){
29 parent[i]=i,rank[i]=0;
30 Root[i]=i;
31
}
32}
33
34
35int union_find::Find(int x)
36{
37 if(parent[x]!=x){
38 parent[x]=Find(parent[x]);
39 }
40 return parent[x];
41}
42
43
44int union_find::Virtual(int x)
45{
46 return Root[Find(x)];
47}
48
49
50int union_find::Union(int x, int y)
51{
52 x=Find(x);
53 y=Find(y);
54 if(x==y){printf("error\n");return 0;}
55 Root[ x]=Root[y];
56 if(rank[x]<rank[y]){
57 parent[x]=y;
58// return y;
59 }
60 else{
61 parent[y]=x;
62 if(rank[x]==rank[y])rank[x]++;
63 // return x;
64 }
65 return Root[y];
66}
67
68struct SNode
69{
70 int m;
71 int index;
72};
73
74 int a[1000000];
75 queue<SNode> Q[1000000];
76 int ans[1000000];
77 int out[1000000];
78int main()
79{
80 freopen("offm8.in","r",stdin);
81 time_t begin,end;
82 begin=clock();
83 int N,M;
84 while(scanf("%d %d",&N,&M)!=EOF){
85 for(int i=0;i<N+M;i++){
86 scanf("%d",&a[i]);
87 while(!Q[i].empty () )Q[i].pop ();
88 }
89 int m=0;
90 union_find U(N);
91 int R=a[0];
92 SNode x;
93 for(int i=1;i<N+M;i++){
94 if(a[i]!=-1){
95 if(a[i-1]!=-1)
96 R=U.Union (a[i-1],a[i]);
97 else
98 R=a[i];
99 }
100 else{
101 x.index =i;
102 x.m=m++;
103 // printf("%d\n ",R);
104 Q[R].push (x);
105 }
106 }
107 // printf("debug\n");
108 for(int i=1;i<=N;i++){
109 int root=U.Virtual (i);
110 if( Q[root].empty ())continue;
111 x=Q[root].front ();Q[root].pop ();
112 ans[ x.m ]=i;
113
114 if(Q[root].empty () && x.index+1<N+M){
115 // union
116 U.Union (i,a[x.index +1]);
117 }
118 }
119 end=clock();
120 cout<<"runtime: "<<double(end-begin)/CLOCKS_PER_SEC<<endl;
121 freopen("offm8.out","r",stdin);
122
123 for(int i=0;i<M;i++)
124 scanf("%d",&out[i]);
125 /**//*for(;i<M-1;i++)
126 printf("%d ",ans[i]);
127 printf("%d\n",ans[i]);
128*/
129 bool suc=true;
130
131 for(int i=0;i<M;i++){
132 if(ans[i]!=out[i]){
133 printf("%d %d\n",ans[i],out[i]);
134 suc=false;
135 }
136 }
137 if(suc)printf("congratulation!\n");
138
139 }
140 return 0;
141}
142
143
144
145
146
147
148
149
150posted on 2009-07-26 12:45
iyixiang 阅读(389)
评论(0) 编辑 收藏 引用 所属分类:
acm