Submission #2530154
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){ if(find_train(x) == find_train(y)) return find_way(x) == find_way(y); return false; } 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 | 1579 Byte |
Status | TLE |
Exec Time | 2104 ms |
Memory | 8064 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 | 3 ms | 5888 KB |
subtask0_1.txt | AC | 2 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 | 2103 ms | 7936 KB |
subtask1_14.txt | TLE | 2103 ms | 7552 KB |
subtask1_2.txt | TLE | 2103 ms | 7424 KB |
subtask1_3.txt | TLE | 2104 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 |