Submission #1184440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184440		kiwimsy	Parachute rings (IOI12_rings)	C++20	37 / 100	2249 ms	173100 KiB

rings

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

int N, cycles, lastcycle;
vector<int> maxdegree(5, 0);
vector<int> candidates, edgeA, edgeB, compsize;
vector<bool> valid(4, true);
vector<vector<int>> parent(5), height(5);
vector<vector<int>> adj, prefix;
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(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){
    newcomp = compsize[pa] + compsize[pb];
    compsize[parent[i][A]] = newcomp;
    compsize[parent[i][B]] = newcomp;
  }
}

void OmitCandidates(){
  for(int i = 0; i < 4; i++){
    vector<vector<int>> nadj(N);
    for(int j = 0; j < edgeA.size(); j++){
      if(edgeA[j] == candidates[i] || edgeB[j] == candidates[i]) continue;
      nadj[edgeA[j]].push_back(edgeB[j]);
      nadj[edgeB[j]].push_back(edgeA[j]);
      maxdegree[i+1] = max(maxdegree[i+1], (int)max(nadj[edgeA[j]].size(), nadj[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);
    }
    for(int j : adj[candidates[i]]) prefix[i][j]++;
  }
}

void Init(int N_) {
  N = N_;
  parent.assign(5, vector<int>(N)), height.assign(5, vector<int>(N)), adj.resize(N); prefix.assign(4, vector<int>(N, 0)), 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
      lastcycle = compsize[parent[0][A]];
      cycles++;
    }
    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{
    adj[A].push_back(B);
    adj[B].push_back(A);
    for(int i = 1; i < 5; i++){
      if(!valid[i-1] || candidates[i-1] == A || candidates[i-1] == B) continue;
      int degA = adj[A].size() - prefix[i-1][A], degB = adj[B].size() - prefix[i-1][B];
      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>= 2) ret = 0;
    else{
      if(cycles == 1) ret = lastcycle;
      else ret = N;
    }
  }
  else{
    for(bool i : valid) ret += i;
  }
  return ret;
}

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