Submission #102998

#	Time	Username	Problem	Language	Result	Execution time	Memory
102998		wxh010910	Parachute rings (IOI12_rings)	C++17	100 / 100	3024 ms	80728 KiB

rings

#include <bits/stdc++.h>

using namespace std;

class dsu {
 public:
  vector<int> p, sz, deg;
  bool ans;

  void init(int n) {
    p.resize(n);
    sz.resize(n);
    deg.resize(n);
    ans = true;
    for (int i = 0; i < n; ++i) {
      p[i] = i;
      sz[i] = 1;
      deg[i] = 0;
    }
  }

  inline int find(int x) {
    while (x != p[x]) {
      x = p[x] = p[p[x]];
    }
    return x;
  }

  void unite(int x, int y) {
    ++deg[x];
    ++deg[y];
    if (deg[x] == 3 || deg[y] == 3) {
      ans = false;
    }
    x = find(x);
    y = find(y);
    if (x == y) {
      ans = false;
    } else {
      p[x] = y;
      sz[y] += sz[x];
    }
  }
};

vector<pair<int, int>> edges;
vector<int> ban(4, -1);
int n, ans, cycles;
vector<dsu> f(5);
bool stage;

void Init(int N) {
  n = N;
  for (int i = 0; i < 5; ++i) {
    f[i].init(N);
  }
}

void Link(int A, int B) {
  edges.emplace_back(A, B);
  if (!stage) {
    if (cycles > 1) {
      return;
    }
    if (f[4].deg[A] < f[4].deg[B]) {
      swap(A, B);
    }
    ++f[4].deg[A];
    ++f[4].deg[B];
    if (f[4].deg[A] == 3) {
      int ptr = 0;
      ban[ptr++] = A;
      for (auto p : edges) {
        if (p.first == A) {
          ban[ptr++] = p.second;
        }
        if (p.second == A) {
          ban[ptr++] = p.first;
        }
        if (ptr == 4) {
          break;
        }
      }
      for (int i = 0; i < 4; ++i) {
        for (auto p : edges) {
          if (p.first != ban[i] && p.second != ban[i]) {
            f[i].unite(p.first, p.second);
          }
        }
      }
      stage = true;
      return;
    }
    int a = f[4].find(A), b = f[4].find(B);
    if (a == b) {
      ++cycles;
      ans = f[4].sz[a];
    } else {
      f[4].p[a] = b;
      f[4].sz[b] += f[4].sz[a];
    }
  } else {
    for (int i = 0; i < 4; ++i) {
      if (A != ban[i] && B != ban[i]) {
        f[i].unite(A, B);
      }
    }
  }
}

int CountCritical() {
  if (!stage) {
    if (cycles == 0) {
      return n;
    } else if (cycles == 1) {
      return ans;
    } else {
      return 0;
    }
  } else {
    int ans = 0;
    for (int i = 0; i < 4; ++i) {
      if (f[i].ans) {
        ++ans;
      }
    }
    return ans;
  }
}

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 31 / 31