Submission #2529801


Source Code Expand

#include<iostream>
using ll = int;
#define MAX_N 100000
using namespace std;

ll par_way[MAX_N],r_way[MAX_N];
ll par_train[MAX_N],r_train[MAX_N];

void init_way(ll n){
	for(ll i=0;i<n;i++){
		par_way[i] = i;
		r_way[i] = 0;
	}
}

ll find_way(ll x){
	if(par_way[x] == x){
		return x;
	}else{
		return par_way[x] = find_way(par_way[x]);
	}
}

void unite_way(ll x,ll y){
	x = find_way(x);
	y = find_way(y);
	if(x==y)	return;
	if(r_way[x]<r_way[y]){
		par_way[x] = y;
	}
	else{
		par_way[y] = x;
		if(r_way[x] == r_way[y])	r_way[x]++;
	}
}

bool same_way(ll x,ll y){
	return find_way(x) == find_way(y);
}

void init_train(ll n){
	for(ll i=0;i<n;i++){
		par_train[i] = i;
		r_train[i] = 0;
	}
}

ll find_train(ll x){
	if(par_train[x] == x){
		return x;
	}else{
		return par_train[x] = find_train(par_train[x]);
	}
}

void unite_train(ll x,ll y){
	x = find_train(x);
	y = find_train(y);
	if(x==y)	return;
	if(r_train[x]<r_train[y]){
		par_train[x] = y;
	}
	else{
		par_train[y] = x;
		if(r_train[x] == r_train[y])	r_train[x]++;
	}
}

bool same_train(ll x,ll y){
	return find_train(x) == find_train(y);
}

int main(void){
	ll N,K,L,x,y;
	cin >> N >> K >> L;
	init_train(N);init_way(N);
	while(K--){
		cin >> x >> y;
		unite_way(x,y);
	}
	while(L--){
		cin >> x >> y;
		unite_train(x,y);
	}
	for(ll i=1;i<=N;i++){
		ll ans=0;
		for(ll j=1;j<=N;j++){
			if(same_train(i,j)&&same_way(i,j))	ans++;
		}
		cout << ans << ' ';
	}
	cout << endl;
	return 0;
}

Submission Info

Submission Time
Task D - Connectivity
User thash
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1536 Byte
Status RE
Exec Time 215 ms
Memory 1792 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 3
AC × 6
RE × 12
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 1 ms 256 KB
subtask0_1.txt AC 1 ms 256 KB
subtask0_2.txt AC 1 ms 256 KB
subtask1_0.txt AC 167 ms 256 KB
subtask1_1.txt RE 97 ms 1792 KB
subtask1_10.txt AC 198 ms 256 KB
subtask1_11.txt RE 97 ms 1792 KB
subtask1_12.txt RE 98 ms 1792 KB
subtask1_13.txt RE 97 ms 1792 KB
subtask1_14.txt RE 97 ms 1792 KB
subtask1_2.txt RE 97 ms 1792 KB
subtask1_3.txt RE 98 ms 1792 KB
subtask1_4.txt RE 99 ms 1792 KB
subtask1_5.txt AC 215 ms 256 KB
subtask1_6.txt RE 97 ms 1792 KB
subtask1_7.txt RE 97 ms 1792 KB
subtask1_8.txt RE 98 ms 1792 KB
subtask1_9.txt RE 97 ms 1792 KB