Submission #1152207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152207		Sofiatpc	Parachute rings (IOI12_rings)	C++20	100 / 100	670 ms	121688 KiB

rings

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
const int MAXN = 1e6+5;
vector<int> cand, ea, eb, adj[MAXN];
int pai[10][MAXN], tam[10][MAXN], grau[10][MAXN], dr[10], n, flag;

void Init(int N_) {
  n = N_;

  cand.clear(); ea.clear(); eb.clear();
  for(int i = 0; i < n; i++)adj[i].clear();

  for(int x = 0; x < 5; x++){
    for(int i = 0; i < n; i++){
      pai[x][i] = i;
      tam[x][i] = 1;
      grau[x][i] = 0;
    }
    dr[x] = 0;
  }
  
}

int find(int id, int x){
  if(pai[id][x] == x)return x;
  return pai[id][x] = find(id, pai[id][x]);
}

void merge(int id, int a, int b){
  a = find(id,a), b = find(id,b);
  if(a == b)return;

  if(tam[id][a] < tam[id][b])swap(a,b);
  pai[id][b] = a;
  tam[id][a] += tam[id][b];
}

void reconstuir(int id, int x){
  for(int i = 0; i < n; i++){
    pai[id][i] = i;
    tam[id][i] = 1;
    grau[id][i] = 0;
  }
  dr[id] = 0;

  for(int i = 0; i < sz(ea); i++){
    int a = ea[i], b = eb[i];
    if(a == x || b == x)continue;

    if(find(id,a) == find(id,b)){dr[id] = 1; return;}

    if(grau[id][a] > 1 || grau[id][b] > 1){dr[id] = 1; return;}
    merge(id,a,b);
    grau[id][a]++; grau[id][b]++;
  }
}

void checarGrau(int a){
  if(grau[0][a] == 4 && (!flag || sz(cand) > 1)){
    cand.clear();
    cand.push_back(a);
    reconstuir(1,a);
    flag = 1;
  }else if(grau[0][a] == 3 && !flag){
    cand.clear();
    cand.push_back(a);
    for(int viz : adj[a])cand.push_back(viz);
    for(int i = 0; i < sz(cand); i++)
      reconstuir(i+1,cand[i]);
    flag = 1;
  }
}

void Link(int a, int b) {
  grau[0][a]++; grau[0][b]++;
  adj[a].push_back(b); adj[b].push_back(a);

  checarGrau(a);
  checarGrau(b);

  ea.push_back(a); eb.push_back(b);

  if(find(0,a) == find(0,b)){
    if(dr[0] == 0)dr[0] = a;
    else dr[0] = -1;
  }
  merge(0,a,b);

  if(flag){
    for(int i = 0; i < sz(cand); i++){
      if(dr[i+1] || a == cand[i] || b == cand[i])continue;

      if(find(i+1,a) == find(i+1,b)){dr[i+1] = 1; continue;}

      if(grau[i+1][a] > 1 || grau[i+1][b] > 1){dr[i+1] = 1; continue;}

      merge(i+1,a,b);
      grau[i+1][a]++; grau[i+1][b]++;
    }
  }
}

int CountCritical(){
  if(!flag){
    if(dr[0] == -1)return 0;
    if(dr[0] == 0)return n;
    return tam[0][find(0,dr[0])];
  }else{
    int ans = 0;
    for(int i = 0; i < sz(cand); i++){
      if(!dr[i+1])ans++;
    }
    return ans;
  }
}

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