Submission #1164009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164009		HappyCapybara	Parachute rings (IOI12_rings)	C++20	0 / 100	237 ms	87084 KiB

rings

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

vector<int> p;

int find(int a){
  if (a == p[a]) return p[a];
  return p[a] = find(p[a]);
}

void merge(int a, int b){
  a = find(a);
  b = find(b);
  if (a == b) return;
  p[b] = a;
}

bool ol = false;
int n, nc;
vector<int> deg;
unordered_set<int> s, cycle;
vector<vector<int>> g;

void Init(int N) {
  n = N;
  nc = -1;
  deg.resize(n, 0);
  for (int i=0; i<n; i++){
    s.insert(i);
    g.push_back({i});
    p.push_back(i);
  }
}

void path(int a, int b){
  vector<int> par(n, -1);
  par[a] = a;
  queue<int> q;
  q.push(a);
  while (!q.empty()){
    int cur = q.front();
    q.pop();
    if (cur == b){
      cycle.insert(b);
      while (cur != a){
        cycle.insert(par[cur]);
        cur = par[cur];
      }
      return;
    }
    for (int next : g[cur]){
      if (par[next] == -1 && next != cur){
        par[next] = cur;
        q.push(next);
      }
    }
  }
}

void Link(int A, int B){
  if (s.empty()) return;
  deg[A]++;
  deg[B]++;
  if (deg[A] == 4){
    if (s.find(A) != s.end()){
      s.clear();
      s.insert(A);
    }
    else s.clear();
  }
  if (deg[B] == 4){
    if (s.find(B) != s.end()){
      s.clear();
      s.insert(B);
    }
    else s.clear();
  }
  if (deg[A] == 3){
    for (int x : s){
      if (count(g[A].begin(), g[A].end(), x) == 0) s.erase(x);
    }
  }
  if (deg[B] == 3){
    for (int x : s){
      if (count(g[B].begin(), g[B].end(), x) == 0) s.erase(x);
    }
  }
  if (s.empty()) return;
  if (find(A) == find(B)){
    if (ol){
      s.clear();
      return;
    }
    if (nc == -1){
      cycle.clear();
      path(A, B);
      /*for (int x : cycle) cout << x << " ";
      cout << endl;*/
      for (int x : s){
        if (cycle.find(x) == cycle.end()) s.erase(x);
      }
      if (s.empty()) return;
      nc = find(A);
    }
    else if (nc >= 0){
      if (find(A) != nc){
        s.clear();
        return;
      }
      cycle.clear();
      path(A, B);
      for (int x : s){
        if (cycle.find(x) == cycle.end()) s.erase(x);
      }
      nc = -2;
    }
    else if (nc == -2){
      if (s.size() != 1){
        s.clear();
        return;
      }
    }
  }
  if (s.empty()) return;
  if (!ol || (A != *s.begin() && B != *s.begin())) merge(A, B);
  g[A].push_back(B);
  g[B].push_back(A);

  if (s.size() == 1 && !ol){
    ol = true;
    for (int i=0; i<n; i++) p[i] = i;
    for (int i=0; i<n; i++){
      if (i == *s.begin()) continue;
      for (int j : g[i]){
        if (j == *s.begin()) continue;
        merge(i, j);
      }
    }
  }
}

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

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