Submission #2530150


Source Code Expand

#include<iostream>
using ll = long long;
#define MAX_N 201010
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]++;
	}
}
	
	
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(ll x,ll y){
	return (find_train(x) == find_train(y))&&(find_way(x) == find_way(y));
}
	
int main(void){
	ll N,K,L,x,y,memo[MAX_N]={};
	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=i;j<=N;j++){
			if(same(i,j)){
					memo[i]++;
					memo[j]++;
			}
		}
	}
	for(ll i=1;i<=N;i++)	cout << memo[i]-1 << ' ';
	cout << endl;
	return 0;
}

Submission Info

Submission Time
Task D - Connectivity
User thash
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1564 Byte
Status TLE
Exec Time 2104 ms
Memory 8064 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 3
AC × 6
TLE × 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 3 ms 5888 KB
subtask0_1.txt AC 3 ms 5888 KB
subtask0_2.txt AC 3 ms 5888 KB
subtask1_0.txt AC 114 ms 6016 KB
subtask1_1.txt TLE 2103 ms 7936 KB
subtask1_10.txt AC 130 ms 6016 KB
subtask1_11.txt TLE 2103 ms 7680 KB
subtask1_12.txt TLE 2103 ms 7808 KB
subtask1_13.txt TLE 2104 ms 7936 KB
subtask1_14.txt TLE 2103 ms 7552 KB
subtask1_2.txt TLE 2103 ms 7424 KB
subtask1_3.txt TLE 2103 ms 7936 KB
subtask1_4.txt TLE 2103 ms 7680 KB
subtask1_5.txt AC 139 ms 6016 KB
subtask1_6.txt TLE 2103 ms 7680 KB
subtask1_7.txt TLE 2103 ms 7936 KB
subtask1_8.txt TLE 2103 ms 8064 KB
subtask1_9.txt TLE 2103 ms 7424 KB