Advertisement
erek1e

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

Jul 1st, 2022
1,141
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.23 KB | None
  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';
  45.                 else if (badRoots.size() == 1) cout << -parent[0][badRoots[0]] << '\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. }
Advertisement
RAW Paste Data Copied
Advertisement