Submission #372912

#	Time	Username	Problem	Language	Result	Execution time	Memory
372912		WLZ	Parachute rings (IOI12_rings)	C++14	0 / 100	1592 ms	84188 KiB

rings

#include <bits/stdc++.h>
using namespace std;

int n, phase = 0;
vector<int> p, sz, cyc;
vector< vector<int> > g;
vector< pair<int, int> > edges;

class candidate {
  private: 
    int u;
    bool pos = true;
    vector<int> p, deg;

    int root(int x) {
      if (p[x] == -1) return x;
      return p[x] = root(p[x]);
    }
  public:
    candidate(int _u) {
      p.assign(n, -1);
      deg.assign(n, 0);
      u = _u;
    }

    void add_edge(int x, int y) {
      if (x == u || y == u) return;
      if (++deg[x] > 2) pos = false;
      if (++deg[y] > 2) pos = false;
      x = root(x); y = root(y);
      if (x == y) pos = false;
      else p[y] = x;
    }

    operator int() const {
      return pos;
    }
};

vector<candidate> candidates;

int root(int x) {
  if (p[x] == -1) return x;
  return p[x] = root(p[x]);
}

void connect(int x, int y) {
  x = root(x); y = root(y);
  if (x == y) cyc.push_back(x);
  else {
    p[y] = x; sz[x] += sz[y];
  }
}

void Init(int N_) {
  n = N_;
  p.assign(n, -1);
  sz.assign(n, 1);
  g.resize(n);
}

void Link(int A, int B) {
  if (phase == 0) {
    g[A].push_back(B);
    g[B].push_back(A);
    edges.push_back({A, B});
    if ((int) g[A].size() < (int) g[B].size()) swap(A, B);
    if ((int) g[A].size() == 3) {
      phase = 1;
      candidates.emplace_back(A);
      for (auto& x : g[A]) candidates.emplace_back(x);
      for (auto& e : edges) for (auto& c : candidates) c.add_edge(e.first, e.second);
    }
  } else {
    for (auto& c : candidates) c.add_edge(A, B);
  }
}

int CountCritical() {
  if (phase == 0) {
    if (cyc.empty()) return n;
    if ((int) cyc.size() > 1) return 0;
    return sz[root(cyc[0])];
  } else {
    int ans = 0;
    for (auto& c : candidates) ans += c;
    return ans;
  }
}

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