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
AC × 3
AC × 18
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