Submission #799293

#	Time	Username	Problem	Language	Result	Execution time	Memory
799293		jlallas384	Parachute rings (IOI12_rings)	C++17	0 / 100	519 ms	50564 KiB

rings

        #include <bits/stdc++.h>
        using namespace std;
         
        vector<vector<int>> g;
        int n;
        vector<int> deg;
         
        void Init(int N){
            n = N;
            g.resize(n);
            deg.assign(n, 0);
        }
         
        vector<int> cc, vis;
        int cyc = 0;
        void dfs(int v, int p, int gg = 1){
            vis[v] = 1;
            if(gg) cc.push_back(v);
            for(int u: g[v]){
                if(!vis[u]) dfs(u, v, gg);
                else if(vis[u] == 1 && u != p){
                	cyc = 1;
                }
            }
        }
         
        int CountCritical(){    
            vis.assign(n, 0);
            int ans = 0;
            int cnt = 0;
            int has = 0;
            int d4 = 0;
            for(int i = 0; i < n; i++){
                cnt += deg[i] >= 3;
                if(d4 && deg[i] > 3) return 0;
                d4 |= deg[i] > 3;
            }
            for(int i = 0; i < n; i++) if(!vis[i]){
                cc.clear();
                cyc = 0;
                dfs(i, -1);
                int t3 = 0;
                for(int v: cc){
                    if(deg[v] >= 3) t3 = 1;
                }
                if(t3 || cyc){
                    if(has) return 0;
                    has = 1;
                    ans = 0;
                    int mx = 0;
                    for(int v: cc){
                        mx = max(mx, deg[v]);
                    }
                    if(mx == 2) ans += cc.size();
                    else{
                        int nw = 0;
                        set<int> st;
                        for(int v: cc){
                        	st.insert(v);
                        }
                        for(int v: cc) if(deg[v] == mx){
                        	set<int> stn;
                        	if(st.count(v)) stn.insert(v);
                        	for(int u: g[v]){
                        		if(st.count(u)) stn.insert(u);
                        	}
                        	st = stn;
                        }
                        for(int v: st) if(deg[v] == mx || mx == 3){
                            for(int x: cc){
                                vis[x] = 0;
                            }
                            vis[v] = 2;
                            cyc = 0;
                            for(int x: cc) if(!vis[x]){
                                dfs(x, -1, 0);
                            }
                            if(cyc == 0){
                                int t = cnt - (deg[v] >= 3); 
                                for(int u: g[v]){
                                    t -= (deg[u] == 3);
                                }
                                nw += (t == 0);
                            }
                        }
                        if(nw == 0) return 0;
                        else ans += nw;
                    }
                }else{
                    if(!has){
                        int nw = 0;
                        int hv = 0;
                        for(int v: cc){
                            int t = cnt - (deg[v] >= 3); 
                            hv |= deg[i] >= 3;
                            for(int u: g[v]){
                                t -= (deg[u] == 3);
                            }
                            nw += (t == 0);
                        }
                        if(nw == 0) return 0;
                        else{
                            ans += nw;
                        }
                    }
                }
            }
            return ans;
        }
         
        void Link(int a, int b){
            g[a].push_back(b);
            g[b].push_back(a);
            deg[a]++;
            deg[b]++;
        }

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