Submission #1188698
Source Code Expand
#include<bits/stdc++.h> #define range(i,a,b) for(int i = (a); i < (b); i++) #define rep(i,b) for(int i = 0; i < (b); i++) #define all(a) (a).begin(), (a).end() #define show(x) cerr << #x << " = " << (x) << endl; #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; const int INF = 2000000000; using namespace std; const int gmax_n = 200005; int par[gmax_n]; //親 int depth[gmax_n];//木の深さ void init(int n){ rep(i,n){ par[i] = i; depth[i] = 0; } } int find(int x){ if(par[x] == x){ return x; }else { return par[x] = find(par[x]); } } void unite(int x, int y){ x = find(x); y = find(y); if(x == y) return; if(depth[x] < depth[y]){ par[x] = y; }else{ par[y] = x; if(depth[x] == depth[y]) depth[x]++; } } bool same(int x, int y){ return find(x) == find(y); } int main(){ int n, k, l; cin >> n >> k >> l; init(n); rep(i,k){ int a, b; cin >> a >> b; a--; b--; unite(a,b); } int ans[gmax_n] = {0}; rep(i,l){ int a, b; cin >> a >> b; a--; b--; if(same(a,b)){ ans[a] = max(ans[a] + 1, ans[b] + 1); ans[b] = ans[a]; } } rep(i,n){ if(i) cout << ' '; cout << ans[i] + 1; } cout << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - Connectivity |
User | noy72 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1479 Byte |
Status | WA |
Exec Time | 160 ms |
Memory | 2944 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 | 2 ms | 1024 KB |
subtask0_1.txt | AC | 2 ms | 1024 KB |
subtask0_2.txt | AC | 2 ms | 1024 KB |
subtask1_0.txt | WA | 112 ms | 1024 KB |
subtask1_1.txt | WA | 130 ms | 2944 KB |
subtask1_10.txt | WA | 110 ms | 1024 KB |
subtask1_11.txt | WA | 125 ms | 2688 KB |
subtask1_12.txt | WA | 126 ms | 2816 KB |
subtask1_13.txt | WA | 142 ms | 2944 KB |
subtask1_14.txt | WA | 159 ms | 2560 KB |
subtask1_2.txt | WA | 119 ms | 2432 KB |
subtask1_3.txt | WA | 144 ms | 2944 KB |
subtask1_4.txt | WA | 160 ms | 2560 KB |
subtask1_5.txt | WA | 115 ms | 1024 KB |
subtask1_6.txt | WA | 119 ms | 2560 KB |
subtask1_7.txt | WA | 123 ms | 2944 KB |
subtask1_8.txt | WA | 152 ms | 2944 KB |
subtask1_9.txt | WA | 155 ms | 2304 KB |