Submission #1611115
Source Code Expand
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <cstring> #include <map> using namespace std; typedef long long ll; const int MAXn = 1000 * 1000 + 13, N = 2 * 100 * 1000 + 13; vector<int> adj1[MAXn], adj2[MAXn], news; ll cmp1[MAXn], cmp2[MAXn], cnt1, cnt2; bool mark1[MAXn], mark2[MAXn]; map<pair<ll, ll>, ll> ans; void bfs1(int r){ queue<int> q; q.push(r); mark1[r] = true; while(!q.empty()){ int v = q.front(); q.pop(); cmp1[v] = cnt1; for(int i = 0; i < adj1[v].size(); i++){ int u = adj1[v][i]; if(!mark1[u]){ mark1[u] = true; q.push(u); } } } } void bfs2(int r){ queue<int> q; q.push(r); mark2[r] = true; while(!q.empty()){ int v = q.front(); q.pop(); cmp2[v] = cnt2; for(int i = 0; i < adj2[v].size(); i++){ int u = adj2[v][i]; if(!mark2[u]){ mark2[u] = true; q.push(u); } } } } int main(){ int n, k, l; cin >> n >> k >> l; for(int i = 0; i < k; i++){ int x, y; cin >> x >> y; x--; y--; adj1[x].push_back(y); adj1[y].push_back(x); } for(int i = 0; i < l; i++){ int x, y; cin >> x >> y; x--; y--; adj2[x].push_back(y); adj2[y].push_back(x); } for(int i = 0; i < n; i++) cmp1[i] = cmp2[i] = -1; cnt1 = cnt2 = 1; memset(mark1, 0, sizeof mark1); memset(mark2, 0, sizeof mark2); for(int i = 0; i < n; i++) if(!mark1[i]){ bfs1(i); cnt1++; } for(int i = 0; i < n; i++) if(!mark2[i]){ bfs2(i); cnt2++; } for(int i = 0; i < n; i++) ans[make_pair(cmp1[i], cmp2[i])]++; for(int i = 0; i < n; i++) cout << ans[make_pair(cmp1[i], cmp2[i])] << " "; cout << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Connectivity |
User | vjudge3 |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 1645 Byte |
Status | AC |
Exec Time | 325 ms |
Memory | 73252 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 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 | 18 ms | 52352 KB |
subtask0_1.txt | AC | 18 ms | 52352 KB |
subtask0_2.txt | AC | 18 ms | 52352 KB |
subtask1_0.txt | AC | 106 ms | 54784 KB |
subtask1_1.txt | AC | 298 ms | 70784 KB |
subtask1_10.txt | AC | 112 ms | 55040 KB |
subtask1_11.txt | AC | 325 ms | 69376 KB |
subtask1_12.txt | AC | 229 ms | 71876 KB |
subtask1_13.txt | AC | 254 ms | 72672 KB |
subtask1_14.txt | AC | 246 ms | 70912 KB |
subtask1_2.txt | AC | 199 ms | 69000 KB |
subtask1_3.txt | AC | 253 ms | 72892 KB |
subtask1_4.txt | AC | 251 ms | 71808 KB |
subtask1_5.txt | AC | 114 ms | 55040 KB |
subtask1_6.txt | AC | 259 ms | 68736 KB |
subtask1_7.txt | AC | 242 ms | 72784 KB |
subtask1_8.txt | AC | 255 ms | 73252 KB |
subtask1_9.txt | AC | 222 ms | 68096 KB |