Submission #988610

#	Time	Username	Problem	Language	Result	Execution time	Memory
988610		huutuan	Parachute rings (IOI12_rings)	C++14	0 / 100	4034 ms	10688 KiB

rings

#include <bits/stdc++.h>

using namespace std;

struct DSU{
   int n, cnt, idx;
   vector<int> lab, cyc;
   void init(int _n){
      n=_n; cnt=0;
      lab.assign(n+1, -1);
      cyc.assign(n+1, 0);
      idx=-1;
   }
   int find_set(int u){
      return lab[u]<0?u:lab[u]=find_set(lab[u]);
   }
   void union_sets(int u, int 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;
         cnt-=cyc[u]; cnt-=cyc[v];
         cnt+=(cyc[u]+=cyc[v]); cyc[v]=0;
      }else cnt-=cyc[u], cnt+=(cyc[u]+=1);
      if (cyc[u]) idx=u;
   }
} dsu;

const int N=1e6+10;
int n, deg[N];
vector<pair<int, int>> edge;
bool check;

void Init(int N_) {
   n=N_;
}

void build(int u){
   check=1;
   dsu.init(n);
   for (auto &i:edge){
      if (i.first==u || i.second==u) continue;
      ++deg[i.first]; ++deg[i.second];
      check&=deg[i.first]<=2 && deg[i.second]<=2;
      dsu.union_sets(i.first, i.second);
   }
   check&=dsu.cnt==0;
}

void Link(int u, int v) {
   ++u; ++v;
   edge.emplace_back(u, v);
}

int CountCritical() {
   int ans=0;
   for (int i=1; i<=n; ++i) build(i), ans+=check;
   return ans;
}

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