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 |
|
|
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 |