Submission #1184384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184384		kiwimsy	Parachute rings (IOI12_rings)	C++20	52 / 100	1509 ms	295004 KiB

rings

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

int N;
vector<int> maxdegree(5, 0);
vector<int> candidates, edgeA, edgeB, compsize;
vector<vector<int>> parent(5), height(5);
vector<bool> valid(4, true);
multiset<int> cycles;
vector<vector<int>> adj;
vector<vector<vector<int>>> adjstates;
bool threestate = false;

int find(int node, int i){
  // standard dsu find with the parent compression thing
  if(parent[i][node] != node){
    parent[i][node] = find(parent[i][node], i);
  }
  return parent[i][node];
}

void unite(int A, int B, int i){
  // union by rank :3
  int newcomp = 0;
  int pa = find(A, i), pb = find(B, i);
  if(i == 0) newcomp = compsize[pa] + compsize[pb];
  if(height[i][pa] > height[i][pb]){
    parent[i][pb] = pa;
    height[i][pa] = max(height[i][pa], height[i][pb] + 1);
  }
  else{
    parent[i][pa] = pb;
    height[i][pb] = max(height[i][pb], height[i][pa] + 1);
  }
  if(i == 0) compsize[parent[i][A]] = newcomp;
  if(i == 0) compsize[parent[i][B]] = newcomp;
}

void OmitCandidates(){
  for(int i : candidates) cerr << i << ' ';
  cerr << endl;
  for(int i = 0; i < 4; i++){
    for(int j = 0; j < edgeA.size(); j++){
      if(edgeA[j] == candidates[i] || edgeB[j] == candidates[i]) continue;
      adjstates[i][edgeA[j]].push_back(edgeB[j]);
      adjstates[i][edgeB[j]].push_back(edgeA[j]);
      maxdegree[i+1] = max(maxdegree[i+1], (int)max(adjstates[i][edgeA[j]].size(), adjstates[i][edgeB[j]].size()));
      if(maxdegree[i+1] >= 3) valid[i] = false;
      if(find(edgeA[j], i+1) == find(edgeB[j], i+1)) valid[i] = false;
      else unite(edgeA[j], edgeB[j], i+1);
    }
  }
}

void Init(int N_) {
  N = N_;
  parent.assign(5, vector<int>(N)), height.assign(5, vector<int>(N)), adj.resize(N); adjstates.assign(4, vector<vector<int>>(N)), compsize.assign(N, 1);
  for(int i = 0; i < N; i++) for(int j = 0; j < 5; j++) parent[j][i] = i;
}

void Link(int A, int B) {
  if(!threestate){
    edgeA.push_back(A);
    edgeB.push_back(B);
    if(find(A, 0) == find(B, 0)) { // this is a cycle
      cycles.insert(parent[0][A]);
    }
    else unite(A, B, 0);
    adj[A].push_back(B);
    adj[B].push_back(A);
    int degA = adj[A].size(), degB = adj[B].size();
    maxdegree[0] = max(maxdegree[0], max(degA, degB));
    if(maxdegree[0] == 3){
      threestate = true;
      if(degA == 3){
        candidates.push_back(A);
        for(int i : adj[A]) candidates.push_back(i);
      }
      else if(degB == 3){
        candidates.push_back(B);
        for(int i : adj[B]) candidates.push_back(i);
      }
      OmitCandidates();
    }
  }
  else{
    for(int i = 1; i < 5; i++){
      if(!valid[i-1]) continue;
      if(A != candidates[i-1] && B != candidates[i-1]){
        adjstates[i-1][A].push_back(B);
        adjstates[i-1][B].push_back(A);
        int degA = adjstates[i-1][A].size(), degB = adjstates[i-1][B].size();
        maxdegree[i] = max(maxdegree[i], max(degA, degB));
        if(maxdegree[i] >= 3) valid[i-1] = false;
        else {
          if(find(A, i) == find(B, i)) { // this is a cycle
            valid[i-1] = false;
          } 
          else unite(A, B, i);
        }
      }
    }
  }
}

int CountCritical() {
  int ret = 0;
  if(!threestate){
    if(maxdegree[0] <= 1) ret = N;
    else if(cycles.size() >= 2) ret = 0;
    else{
      if(cycles.size() == 1) ret = compsize[*cycles.begin()];
      else ret = N;
    }
  }
  else{
    for(bool i : valid) ret += i;
  }
  return ret;
}

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