Submission #1189350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189350		yellowtoad	Parachute rings (IOI12_rings)	C++20	37 / 100	596 ms	119240 KiB

rings

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int n, cnt, lst, freq[1000010], p[1000010], deg[1000010], vis[1000010];
bool found, done;
vector<int> edge[1000010], pos, tmp, path, cycle;

int dsu(int u) {
  if (p[u] == u) return u;
  return p[u] = dsu(p[u]);
}

void Init(int N) {
  n = N;
  for (int i = 0; i < n; i++) p[i] = i, pos.push_back(i);
}

void dfs(int u, int tar, int v) {
  if (vis[u]) {
    if (u == tar) cycle = path;
    return;
  }
  path.push_back(u);
  vis[u] = 1;
  for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != v) dfs(edge[u][i],tar,u);
  path.pop_back();
}

void Link(int u, int v) {
  lst = cnt;
  edge[u].push_back(v);
  edge[v].push_back(u);
  if (dsu(u) == dsu(v)) {
    if (found) {
      cnt++;
      freq[u]++;
      freq[v]++;
    } else {
      dfs(u,u,-1);
      cnt++;
      for (int i = 0; i < cycle.size(); i++) freq[cycle[i]]++;
      found = 1;
    }
  } else p[dsu(u)] = dsu(v);
  deg[u]++; deg[v]++;
  if (deg[u] >= 3) {
    cnt++;
    freq[u]++;
    if (deg[u] == 3) for (int i = 0; i < edge[u].size(); i++) freq[edge[u][i]]++;
  }
  if (deg[v] >= 3) {
    cnt++;
    freq[v]++;
    if (deg[v] == 3) for (int i = 0; i < edge[v].size(); i++) freq[edge[v][i]]++;
  }
  if (cnt != lst) {
    tmp.clear();
    for (int i = 0; i < pos.size(); i++) if (freq[pos[i]] == cnt) tmp.push_back(pos[i]);
    pos = tmp;
  }
}

int CountCritical() {
  return pos.size();
}

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