Submission #802146

#	Time	Username	Problem	Language	Result	Execution time	Memory
802146		Dan4Life	낙하산 고리들 (IOI12_rings)	C++17	0 / 100	1118 ms	262144 KiB

rings

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
const int N = (int)1e6+9;
vector<int> v, w;
array<int,2> edges[N];
int n, totE=0, T=1, ok=1;

struct Dsu{
    bool bad[N];
    vector<int> st, adj[N];
    int node, numBad, cycSz;
    int vis[N], p[N], sz[N], deg[N];
    void dfs(int s, int p){
        vis[s]=1; st.pb(s);
        for(auto u : adj[s]){
            if(u==p) continue;
            if(!vis[u]) dfs(u,s);
            else if(vis[u]==1){ cycSz++;
                while(sz(st) and st.back()!=u){
                    cycSz++; st.pop_back();
                }
                return;
            }
        }
        vis[s]=2; st.pop_back();
    }
    void init(int N){
        st.clear(); node = -1; numBad=cycSz=0;
        for(int i = 0; i < N; i++){
            adj[i].clear(); p[i]=i,sz[i]=1;
            bad[i]=vis[i]=deg[i]=0; 
        }
    }
    int findSet(int i){ return i==p[i]?i:p[i]=findSet(p[i]); }
    void unionSet(int i, int j){
        if(i==node or j==node) return;
        deg[i]++, deg[j]++;
        adj[i].pb(j), adj[j].pb(i);
        int x = findSet(i), y = findSet(j);
        if(x==y){
            if(!bad[x]) numBad++, bad[x]=1;
            if(!cycSz) dfs(i,-1); return;
        }
        numBad-=bad[x]+bad[y];
        if(sz[x]<sz[y]) swap(x,y);
        p[y] = x; sz[x]+=sz[y];
        if(!bad[x] and !bad[y]){
            if(deg[i]>2 or deg[j]>2) 
                bad[x]=bad[y]=1;
        }
        else bad[x]=bad[y]=1;
        numBad+=bad[x];
    }
} dsu[5];

void Init(int n_) { n = n_; for(int i=0;i<5;i++) dsu[i].init(n); }

void Link(int a, int b) {
    edges[totE++]={a,b};
    for(int i = 0; i < T; i++) 
        dsu[i].unionSet(a,b);
    if(dsu[0].deg[a]==4)v.pb(a);
    if(dsu[0].deg[b]==4)v.pb(b);
    if(dsu[0].deg[a]==3)w.pb(a);
    if(dsu[0].deg[b]==3)w.pb(b);
}

int CountCritical(){
    if(sz(v)>=2 or dsu[0].numBad>=2) return 0;
    if(!dsu[0].numBad) return n;
    if(sz(v)==1){
        if(ok){
            dsu[T++].node = v[0]; ok=0;
            for(int i = 0; i < totE; i++)
                dsu[1].unionSet(edges[i][0],edges[i][1]);
        }
        return !dsu[1].numBad;
    }
    if(sz(w)==0) return dsu[0].cycSz;
    if(ok){
        dsu[T++].node=w[0]; ok = 0;
        for(auto u : dsu[0].adj[w[0]]) dsu[T++].node=u;
        for(int j : {1,2,3,4})
          for(int i = 0; i < totE; i++)
              dsu[j].unionSet(edges[i][0],edges[i][1]);
    }
    int ans = 0; for(int i : {1,2,3,4}) ans+=!dsu[i].numBad;
    return ans;
}

Compilation message (stderr)

rings.cpp: In member function 'void Dsu::init(int)':
rings.cpp:33:26: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   33 |             bad[i]=vis[i]=deg[i]=0;
      |                    ~~~~~~^~~~~~~~~
rings.cpp: In member function 'void Dsu::unionSet(int, int)':
rings.cpp:44:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   44 |             if(!cycSz) dfs(i,-1); return;
      |             ^~
rings.cpp:44:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   44 |             if(!cycSz) dfs(i,-1); return;
      |                                   ^~~~~~

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