Submission #988777

#	Time	Username	Problem	Language	Result	Execution time	Memory
988777		huutuan	Parachute rings (IOI12_rings)	C++14	0 / 100	1008 ms	240556 KiB

rings

#include <bits/stdc++.h>

using namespace std;

struct DSU{
   int n, check, idx, cnt, mxdeg;
   vector<int> lab, deg;
   void init(int _n){
      n=_n; check=1; idx=-1; cnt=0; mxdeg=0;
      lab.assign(n+1, -1);
      deg.assign(n+1, 0);
   }
   int find_set(int u){
      return lab[u]<0?u:lab[u]=find_set(lab[u]);
   }
   void union_sets(int u, int v){
      ++deg[u], ++deg[v]; mxdeg=max({mxdeg, deg[u], deg[v]});
      u=find_set(u); v=find_set(v);
      if (u!=v){
         if (lab[u]>lab[v]) swap(u, v);
         lab[u]+=lab[v];
         lab[v]=u;
         if (idx==v) idx=u;
      }else check=0, idx=u, ++cnt;
   }
} dsu[20], dsu2;

const int N=1e6+10;
int n, deg[N];
set<int> st3, st4;
vector<pair<int, int>> edge;
bool cc;
vector<int> cand, g[N];

void Init(int N_) {
   n=N_;
   dsu2.init(n+1);
}

void add_cand(int u){
   if (find(cand.begin(), cand.end(), u)!=cand.end() || (int)cand.size()>20) return;
   int id=cand.size();
   cand.push_back(u);
   if (id<20){
      dsu[id].init(n+1);
      for (auto &i:edge) if (i.first!=u && i.second!=u) dsu[id].union_sets(i.first, i.second);
   }
}

void Link(int u, int v) {
   ++u; ++v;
   edge.emplace_back(u, v);
   if ((int)cand.size()<=20){
      for (int i=0; i<(int)cand.size(); ++i){
         if (u==cand[i] || v==cand[i]) continue;
         dsu[i].union_sets(u, v);
      }
   }
   st3.erase(u); st3.erase(v);
   ++deg[u]; ++deg[v];
   g[u].push_back(v);
   g[v].push_back(u);
   if (deg[u]==3) st3.insert(u);
   if (deg[v]==3) st3.insert(v);
   if (deg[u]==4) st4.insert(u);
   if (deg[v]==4) st4.insert(v);
   if ((int)st3.size()+(int)st4.size()<=10){
      for (int u:st4) add_cand(u);
      for (int u:st3){
         add_cand(u);
         for (int v:g[u]) add_cand(v);
      }
   }
}

int CountCritical() {
   if (st3.empty() && st4.empty()){
      if (dsu2.check) return n;
      if (dsu2.cnt==1) return -dsu2.lab[dsu2.idx];
      return 0;
   }
   if ((int)cand.size()>20) return 0;
   int ans=0;
   for (int i=0; i<(int)cand.size(); ++i){
      ans+=dsu[i].check && dsu[i].mxdeg<=2;
   }
   return ans;
}

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