Submission #1150873

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150873		Sofiatpc	Parachute rings (IOI12_rings)	C++20	0 / 100	13 ms	30340 KiB

rings

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
const int MAXN = 1e6+5;
vector<int> c, ea, eb, adj[MAXN];
int p[5][MAXN], s[5][MAXN], g[5][MAXN], dr[5], n;

void Init(int N_) {
  n = N_;
  for(int i = 0; i < n; i++)c.push_back(i);
  for(int i = 0; i < n; i++){
    p[0][i] = i;
    s[0][i] = 1;
  }
}

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

void merge(int id, int a, int b){
  a = find(id,a), b = find(id,b);
  if(s[id][a] < s[id][b])swap(a,b);
  p[id][b] = a;
  s[id][a] += s[id][b];
}

void reconstuir(int id, int x){
  for(int i = 0; i < n; i++){
    p[id][i] = i;
    s[id][i] = 1;
    g[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(g[id][a] > 1 || g[id][b] > 1){dr[id] = 1; return;}
    merge(id,a,b);
    g[id][a]++; g[id][b]++;
  }
}

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

void Link(int a, int b) {
  g[0][a]++; g[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);

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

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

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

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

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

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