# IOI '12 P2 - Parachute Rings (Standard I/O)

Jul 1st, 2022
1,244
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3.
4. using namespace std;
5.
6. int root(int i, vector<int> &parent) {
7.     return parent[i] < 0 ? i : (parent[i] = root(parent[i], parent));
8. }
9. bool unite(int i, int j, vector<int> &parent) {
10.     i = root(i, parent), j = root(j, parent);
11.     if (i == j) return false;
12.     if (parent[i] > parent[j]) swap(i, j);
13.     parent[i] += parent[j];
14.     parent[j] = i;
15.     return true;
16. }
17.
18. int main() {
19.     int n, l;
20.     cin >> n >> l;
21.     vector<int> parent[4];
22.     parent[0] = vector<int>(1+n, -1);
23.     bool valid[4]{};
24.
25.     vector<vector<int>> degree(1+n);
26.     vector<pair<int, int>> edgeList;
27.     bool deg3 = false; // exists node with degree >= 3
28.     vector<int> badRoots; // roots with cycles - only used when deg3 == false
29.     int candidates = -1; // how many "parent" vectors are being used (only relevant when deg3 == true)
30.     vector<int> cand; // candidates
31.
32.     auto addEdge = [&parent, &valid, &degree, &cand](int c, int u, int v) { // c is index of which parent (dsu) to add to
33.         if (!unite(u, v, parent[c])) valid[c] = false;
34.         int du = 0, dv = 0; // degrees excluding candidate node
35.         for (int w : degree[u]) du += w != cand[c];
36.         for (int w : degree[v]) dv += w != cand[c];
37.         if (du == 3 || dv == 3) valid[c] = false;
38.     };
39.
40.     while (l--) {
41.         int x; cin >> x;
42.         if (x == -1) {
43.             if (!deg3) {
44.                 if (badRoots.empty()) cout << n << '\n';
46.                 else cout << 0 << '\n';
47.             } else {
48.                 int ans = 0;
49.                 for (int c = 0; c < candidates; ++c) ans += valid[c];
50.                 cout << ans << '\n';
51.             }
52.         } else {
53.             int y; cin >> y;
54.             degree[x].push_back(y), degree[y].push_back(x);
55.             edgeList.emplace_back(x, y);
56.             if (!deg3) {
57.                 if (!unite(x, y, parent[0])) badRoots.push_back(root(x, parent[0]));
58.                 if (degree[x].size() == 3 || degree[y].size() == 3) {
59.                     deg3 = true;
60.                     if (degree[x].size() == 3 && degree[y].size() == 3) {
61.                         candidates = 2;
62.                         cand.push_back(x);
63.                         cand.push_back(y);
64.                     } else {
65.                         candidates = 4;
66.                         if (degree[y].size() == 3) swap(x, y);
67.                         cand.push_back(x);
68.                         for (int z : degree[x]) cand.push_back(z);
69.                     }
70.                     // Now construct the new "parent" arrays using the memorized edges
71.                     for (int c = 0; c < candidates; ++c) {
72.                         parent[c] = vector<int>(1+n, -1);
73.                         valid[c] = true;
74.                         for (auto [u, v] : edgeList) {
75.                             if (cand[c] != u && cand[c] != v) addEdge(c, u, v);
76.                         }
77.                     }
78.                 }
79.             } else {
80.                 for (int c = 0; c < candidates; ++c) {
81.                     if (cand[c] != x && cand[c] != y) addEdge(c, x, y);
82.                 }
83.             }
84.         }
85.     }
86.     return 0;
87. }