Submission #532186

#	Time	Username	Problem	Language	Result	Execution time	Memory
532186		AdamGS	Parachute rings (IOI12_rings)	C++17	100 / 100	654 ms	64684 KiB

rings

#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
const int LIM=1e6+7;
pair<int,int>kraw[LIM];
int F[LIM], ile[LIM], deg[LIM], n, q, typ, ans;
vector<int>kand;
int F2[LIM][4], deg2[LIM][4], ok[4];
int fnd(int x) {
  if(F[x]==x) return x;
  return F[x]=fnd(F[x]);
}
int fnd2(int x, int y) {
  if(F2[x][y]==x) return x;
  return F2[x][y]=fnd2(F2[x][y], y);
}
void Init(int N) {
  n=N; ans=n;
  rep(i, n) {
    F[i]=i;
    ile[i]=1;
  }
}
void usun(int x) {
  kand.pb(x);
  rep(i, q) if(kraw[i].st==x || kraw[i].nd==x) kand.pb(kraw[i].st^kraw[i].nd^x);
  typ=2;
  ans=0;
  rep(j, 4) {
    rep(i, n) F2[i][j]=i;
    ok[j]=1;
    rep(i, q) if(kraw[i].st!=kand[j] && kraw[i].nd!=kand[j]) {
      if(fnd2(kraw[i].st, j)==fnd2(kraw[i].nd, j)) ok[j]=0;
      F2[fnd2(kraw[i].st, j)][j]=fnd2(kraw[i].nd, j);
      ++deg2[kraw[i].st][j];
      ++deg2[kraw[i].nd][j];
      if(deg2[kraw[i].st][j]==3 || deg2[kraw[i].nd][j]==3) ok[j]=0;
    }
    ans+=ok[j];
  }
}
void upd(int a, int b) {
  rep(i, 4) if(a!=kand[i] && b!=kand[i] && ok[i]) {
    if(fnd2(a, i)==fnd2(b, i)) {
      ok[i]=0;
      --ans;
      continue;
    }
    F2[fnd2(b, i)][i]=fnd2(a, i);
    ++deg2[a][i];
    ++deg2[b][i];
    if(deg2[a][i]==3 || deg2[b][i]==3) {
      ok[i]=0;
      --ans;
      continue;
    }
  }
}
void Link(int a, int b) {
  if(ans==0) return;
  kraw[q]={a, b};
  ++deg[a]; ++deg[b]; ++q;
  if(typ==2) {
    upd(a, b);
    return;
  }
  if(deg[a]<deg[b]) swap(a, b);
  if(deg[a]==3) {
    usun(a);
    return;
  }
  if(fnd(a)==fnd(b)) {
    if(typ==1) ans=0;
    else {
      typ=1;
      ans=ile[fnd(a)];
    }
    return;
  }
  ile[fnd(a)]+=ile[fnd(b)];
  F[fnd(b)]=fnd(a);
}
int CountCritical() {
  return ans;
}

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