Submission #1189389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189389		yellowtoad	Parachute rings (IOI12_rings)	C++20	20 / 100	3355 ms	327680 KiB

rings

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

int n, cnt, lst, freq[1000010], p[1000010], p2[1000010], deg[1000010], vis[1000010], is[1000010], from[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]);
}

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

void Init(int N) {
  n = N;
  for (int i = 0; i < n; i++) p[i] = p2[i] = i, from[i] = -1, 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 dfs2(int u, int v, int root) {
  from[u] = root;
  for (int i = 0; i < edge[u].size(); i++) if ((!is[edge[u][i]]) && (edge[u][i] != v)) dfs2(edge[u][i],u,root);
}

void Link(int u, int v) {
  if (done) return;
  lst = cnt;
  edge[u].push_back(v);
  edge[v].push_back(u);
  if (found) {
    if (dsu2(u) == dsu2(v)) {
      done = 1;
      return;
    }
    if ((!is[u]) && (!is[v])) p2[dsu2(u)] = dsu2(v);
    if ((from[u] != -1) && (from[v] != -1)) {
      if (from[u] == from[v]) {
        cnt++;
        freq[from[u]]++;
      } else if ((abs(is[from[u]]-is[from[v]]) == 1) || (abs((int)((is[from[u]]%cycle.size())-(is[from[v]]%cycle.size()))) == 1)) {
        cnt++;
        freq[from[u]]++;
        freq[from[v]]++;
      } else {
        done = 1;
        return;
      }
    } else if (from[u] != -1) {
      dfs2(v,u,from[u]);
    } else if (from[v] != -1) {
      dfs2(u,v,from[v]);
    }
  } else {
    if (dsu(u) == dsu(v)) {
      dfs(u,u,-1);
      cnt++;
      for (int i = 0; i < cycle.size(); i++) {
        is[cycle[i]] = i+1;
        freq[cycle[i]]++;
      }
      for (int i = 0; i < cycle.size(); i++) dfs2(cycle[i],-1,cycle[i]);
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < edge[i].size(); j++) {
          if ((is[i]) || (is[edge[i][j]])) continue;
          p2[dsu2(i)] = dsu2(edge[i][j]);
        }
      }
      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() {
  if (done) return 0;
  return pos.size();
}

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