Submission #799294

#	Time	Username	Problem	Language	Result	Execution time	Memory
799294		jlallas384	Parachute rings (IOI12_rings)	C++17	55 / 100	4061 ms	104468 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);
                            }
                                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: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31