oj.uz

Submission #988615

# Submission time Handle Problem Language Result Execution time Memory
988615 2024-05-25T10:02:41 Z huutuan Parachute rings (IOI12_rings) C++14
0 / 100
 977 ms 98816 KB 
#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, dsu2;

const int N=1e6+10;
int deg[N], deg2[N];
int n;
set<int> st3, st4;
set<int> adj;
int cnt3;
vector<int> g[N], cycle, gg[N];
vector<pair<int, int>> edge;
int vis[N], par[N], chk[N];
bool cc;

void Init(int N_) {
   n=N_;
   dsu.init(n);
}

void dfs(int u, int p){
   vis[u]=1;
   par[u]=p;
   for (int v:g[u]) if (v!=p){
      if (!vis[v]) dfs(v, u);
      else if (cycle.empty()){
         int w=u;
         while (w!=v) cycle.push_back(w), w=par[w];
         cycle.push_back(v);
         for (int x:cycle) chk[x]=1;
      }
   }
}

void build(){
   cc=1;
   dsu2.init(n);
   int u=*st4.begin();
   for (auto &i:edge){
      if (i.first==u || i.second==u) continue;
      ++deg2[i.first]; ++deg2[i.second];
      cc&=deg2[i.first]<=2 && deg2[i.second]<=2;
      dsu2.union_sets(i.first, i.second);
   }
}

void Link(int u, int v) {
   ++u; ++v;
   edge.emplace_back(u, v);
   dsu.union_sets(u, v);
   if (st4.size()==1 && u!=*st4.begin() && v!=*st4.begin()){
      ++deg2[u]; ++deg2[v];
      cc&=deg2[u]<=2 && deg2[v]<=2;
      dsu2.union_sets(u, v);
   }
   g[u].push_back(v);
   g[v].push_back(u);
   if (dsu.cnt && cycle.empty()){
      dfs(dsu.idx, 0);
   }
   if (deg[u]==3 && (int)st4.size()==1 && adj.count(u)) --cnt3;
   if (deg[v]==3 && (int)st4.size()==1 && adj.count(v)) --cnt3;
   st3.erase(u); st3.erase(v);
   ++deg[u]; ++deg[v];
   if (deg[u]==3) st3.insert(u);
   if (deg[v]==3) st3.insert(v);
   if (deg[u]>3) st4.insert(u);
   if (deg[v]>3) st4.insert(v);
   if ((deg[u]>3 || deg[v]>3) && st4.size()==1){
      build();
   }
   if (deg[u]<deg[v]) swap(u, v);
   if ((int)st4.size()==1 && *st4.begin()==u){
      adj.insert(v);
      if (deg[v]==3) ++cnt3;
   }
   if (deg[u]==3 && (int)st4.size()==1 && adj.count(u)) ++cnt3;
   if (deg[v]==3 && (int)st4.size()==1 && adj.count(v)) ++cnt3;
}

int CountCritical() {
   if (st3.empty() && st4.empty()){
      if (dsu.cnt==0) return n;
      if (dsu.cnt==1) return -dsu.lab[dsu.idx];
      return 0;
   }
   if ((int)st4.size()>=2) return 0;
   if ((int)st4.size()==1){
      return cc && dsu2.cnt==0;
   }
   if ((int)st3.size()>=5) return 0;
   if (dsu.cnt==2){
      vector<int> v3(st3.begin(), st3.end());
      bool ff=0;
      for (int u:v3) for (int v:v3){
         bool check=1, check2=0;
         set<int> st;
         for (int w:g[u]) if (w!=v) st.insert(w); else check2|=1;
         check&=check2; check&=(int)st.size()==2;
         for (int w:g[v]) if (w!=u) st.insert(w);
         check&=(int)st.size()==2;
         int cnt=0;
         for (int w:st) cnt+=deg[w]==3;
         check&=cnt+2==(int)st3.size();
         ff|=check;
      }
      return ff*2;
   }
   int ans=0;
   if ((int)st3.size()==2 && dsu.cnt==1){
      int u=*st3.begin(), v=*st3.rbegin();
      bool adj=0, cc=0;
      for (int w:g[u]){
         if (w==v){
            adj=1;
         }else{
            cc|=find(g[v].begin(), g[v].end(), w)!=g[v].end();
         }
      }
      if (adj && cc) ++ans;
   }
   for (int u:st3){
      int cnt=0;
      for (int v:g[u]) cnt+=deg[v]==3;
      if (cnt==(int)st3.size()-1 && (!dsu.cnt || (dsu.cnt==1 && chk[u]))) ++ans;
   }
   if ((int)st3.size()==1){
      for (int u:g[*st3.begin()]) ans+=!dsu.cnt || (dsu.cnt==1 && chk[u]); 
   }
   return ans;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 49500 KB Output is correct
2 Correct 15 ms 49756 KB Output is correct
3 Incorrect 17 ms 50012 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 76140 KB Output is correct
2 Incorrect 977 ms 98816 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 49500 KB Output is correct
2 Correct 15 ms 49756 KB Output is correct
3 Incorrect 17 ms 50012 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 49500 KB Output is correct
2 Correct 15 ms 49756 KB Output is correct
3 Incorrect 17 ms 50012 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 49500 KB Output is correct
2 Correct 15 ms 49756 KB Output is correct
3 Incorrect 17 ms 50012 KB Output isn't correct
4 Halted 0 ms 0 KB -