oj.uz

Submission #796642

# Submission time Handle Problem Language Result Execution time Memory
796642 2023-07-28T15:07:38 Z jlallas384 Parachute rings (IOI12_rings) C++17
0 / 100
 720 ms 52076 KB 
#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 bad = 0;
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;
            int rip = cyc;
            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){
                    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;
                	if(st.size() > 3){
	                	if(rip){
	                		if(mx == 3){
	                			ans += 2;
	                		}
	                	}
	                	else{
	                		ans += st.size() - 1;
	                	}
                	}
                }
            }
        }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(hv && 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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 2 ms 596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 32944 KB Output is correct
2 Incorrect 720 ms 52076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 2 ms 596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 2 ms 596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 2 ms 596 KB Output isn't correct
3 Halted 0 ms 0 KB -