Submission #1164043

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164043		HappyCapybara	Parachute rings (IOI12_rings)	C++20	0 / 100	514 ms	105756 KiB

rings

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

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

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

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

void path(int a, int b){
  return;
  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 Init(int N) {
  n = N;
  nc = -1;
  deg.resize(n, 0);
  g.resize(n);
  for (int i=0; i<n; i++){
    s.insert(i);
    g[i].push_back(i);
    p.push_back(i);
  }
  return;
}

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();
      return;
    }
  }
  if (deg[B] == 4){
    if (s.find(B) != s.end()){
      s.clear();
      s.insert(B);
    }
    else {
      s.clear();
      return;
    }
  }
  if (deg[A] == 3){
    unordered_set<int> s2;
    if (s.find(B) != s.end()) s2.insert(B);
    for (int x : g[A]){
      if (s.find(x) != s.end()) s2.insert(x);
    }
    s = s2;
  }
  if (s.empty()) return;
  if (deg[B] == 3){
    unordered_set<int> s2;
    if (s.find(A) != s.end()) s2.insert(A);
    for (int x : g[B]){
      if (s.find(x) != s.end()) s2.insert(x);
    }
    s = s2;
  }
  if (s.empty()) return;
  if (ufind(A) == ufind(B)){
    if (ol){
      s.clear();
      return;
    }
    if (nc == -1){
      cycle.clear();
      path(A, B);
      for (int x : s){
        if (cycle.find(x) == cycle.end()) s.erase(x);
      }
      if (s.empty()) return;
      nc = 0;
    }
    else if (nc == 0){
      cycle.clear();
      path(A, B);
      for (int x : s){
        if (cycle.find(x) == cycle.end()) s.erase(x);
      }
      nc = -2;
      if (s.empty()) return;
    }
    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 (i == j) continue;
        if (j == *s.begin()) continue;
        merge(i, j);
      }
    }
  }*/
  return;
}

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