oj.uz

Submission #372912

# Submission time Handle Problem Language Result Execution time Memory
372912 2021-03-02T09:01:14 Z WLZ Parachute rings (IOI12_rings) C++14
0 / 100
 1592 ms 84188 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Correct 3 ms 752 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 43860 KB Output is correct
2 Correct 952 ms 77204 KB Output is correct
3 Correct 1592 ms 76204 KB Output is correct
4 Incorrect 885 ms 84188 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Correct 3 ms 752 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Correct 3 ms 752 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Correct 3 ms 752 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -