Submission #3221783
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for(int i = 1; i <= n ; i++)
#define MAX_N 200100
int par[2][MAX_N];
int myrank[2][MAX_N];
void init(int n){
rep(i,n){
par[0][i] = par[1][i] = i;
myrank[0][i] = myrank[1][i] =0;
}
}
int find(int x, int z){
return par[z][x]==x?x:par[z][x] = find(par[z][x], z);
}
void unite(int x, int y, int z){
x = find(x,z);
y = find(y,z);
if(x == y) return;
if(myrank[z][x] < myrank[z][y]){
par[z][x] = y;
} else {
par[z][y] = x;
if(myrank[z][x] == myrank[z][y]) myrank[z][x]++;
}
}
signed main(){
int N, K, L, a, b;
unordered_map<int,int> mp;
cin>>N>>K>>L;
init(N+10);
rep(i, K){cin>>a>>b;unite(a,b,0);}
rep(i, L){cin>>a>>b;unite(a,b,1);}
// rep(i,N) mp[find(i,0)*(N+1) + find(i,1)]++;
rep(i,N) mp[find(i,0)*(N+29) + find(i,1)]++;
rep(i,N) cout<<(i-1?" ":"")<<mp[find(i,0)*(N+29)+find(i,1)];
cout<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Connectivity |
User |
Okay |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
994 Byte |
Status |
AC |
Exec Time |
163 ms |
Memory |
14536 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
subtask0_0.txt, subtask0_1.txt, subtask0_2.txt |
All |
subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_0.txt |
AC |
2 ms |
4352 KB |
subtask0_1.txt |
AC |
2 ms |
4352 KB |
subtask0_2.txt |
AC |
2 ms |
4352 KB |
subtask1_0.txt |
AC |
84 ms |
4352 KB |
subtask1_1.txt |
AC |
131 ms |
14536 KB |
subtask1_10.txt |
AC |
88 ms |
4352 KB |
subtask1_11.txt |
AC |
126 ms |
13640 KB |
subtask1_12.txt |
AC |
142 ms |
13384 KB |
subtask1_13.txt |
AC |
156 ms |
14152 KB |
subtask1_14.txt |
AC |
157 ms |
10788 KB |
subtask1_2.txt |
AC |
123 ms |
10788 KB |
subtask1_3.txt |
AC |
157 ms |
14024 KB |
subtask1_4.txt |
AC |
159 ms |
11300 KB |
subtask1_5.txt |
AC |
90 ms |
4352 KB |
subtask1_6.txt |
AC |
119 ms |
13128 KB |
subtask1_7.txt |
AC |
144 ms |
14152 KB |
subtask1_8.txt |
AC |
163 ms |
14152 KB |
subtask1_9.txt |
AC |
147 ms |
9508 KB |