oj.uz

Submission #828094

# Submission time Handle Problem Language Result Execution time Memory
828094 2023-08-17T04:26:12 Z jlallas384 Parachute rings (IOI12_rings) C++17
55 / 100
 4000 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
 
namespace good{
    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]++;
    }
};

namespace bads{
    struct ufds{
        vector<int> sz, par;
        ufds(){}
        ufds(int n): sz(n, 1), par(n){
            iota(par.begin(), par.end(), 0);
        }
        int find(int a){
            return par[a] == a ? a : par[a] = find(par[a]);
        }
        int unite(int a, int b){
            a = find(a), b = find(b);
            if(a == b) return 0;
            if(sz[a] < sz[b]) swap(a, b);
            par[b] = a;
            sz[a] += sz[b];
            return 1;
        }
    };
     
    set<int> ans;
    vector<vector<int>> g, tree;
    vector<int> deg;
    int n;
    ufds ds;
     
    int bad = 0;
    int d4 = 0;
     
    void Init(int N){
        n = N;
        g.resize(n);
        tree.resize(n);
        deg.resize(n);
        for(int i = 0; i < n; i++){
            ans.insert(i);
        }
        ds = ufds(n);
    }
     
    void proc(int a, int add = 1){
        if(deg[a] == 4){
            if(add){
                d4++;
                if(d4 == 2) bad = 1;
            }
            if(!ans.count(a)) ans = {};
            else ans = {a};
        }else if(deg[a] == 3){
            set<int> nans;
            if(ans.count(a)) nans.insert(a);
            for(int u: g[a]){
                if(ans.count(u)) nans.insert(u);
            }
            ans = nans;
        }
    }
     
    int dfs4(int v, int p, vector<int> &vis){
        vis[v] = 2;
        for(int u: g[v]){
            if(!vis[u]){
                if(dfs4(u, v, vis)) return 1;
            }
            else if(vis[u] == 2 && u != p){
                return 1;
            }
        }
        return 0;
    }
    int cyc = 0;
    int CountCritical(){    
     
        if(bad) return 0;
        else{
            for(int x: ans) if(deg[x] > 2){
                vector<int> vis(n);
                vis[x] = 1;
                for(int i = 0; i < n; i++) if(vis[i] == 0){
                    assert(!dfs4(i, -1, vis));
                }
            }
            return ans.size();
        }
    }
     
     
     
     
    vector<int> path;
    int dfs(int v, int p, int x){
        path.push_back(v);
        if(v == x) return 1;
        for(int u: tree[v]) if(u != p){
            if(dfs(u, v, x)) return 1;
        }
        path.pop_back();
        return 0;
    }
     
    void dfs2(int v, set<int> &vis){
        if(ans.count(v)) return;
        vis.insert(v);
        for(int u: g[v]) if(!vis.count(u)){
            dfs2(u, vis);
        }
    }
     
    int dfs3(int v, set<int> &v1, set<int> &v2){
        if(ans.count(v)) return 0;
        if(v1.count(v)) return 1;
        v2.insert(v);
        for(int u: g[v]) if(!v2.count(u)){
            if(dfs3(u, v1, v2)) return 1;
        }
        return 0;
    }
     
     
     
    void Link(int a, int b){
        if(bad) return;
        int res = ds.unite(a, b);
        deg[a]++, deg[b]++;
        g[a].push_back(b);
        g[b].push_back(a);
        proc(a), proc(b);
        if(!res){
            if(!cyc){
                dfs(a, -1, b);
                ans = {};
                for(int x: path){
                    ans.insert(x);
                }
                for(int i = 0; i < n; i++){
                    proc(i, 0);
                }
                cyc = 1;
            }else{
                if(ans.size() >= 3) bad = 1;
                g[a].pop_back();
                g[b].pop_back();
                set<int> v1, v2;
                dfs2(a, v1);
                if(dfs3(b, v1, v2)){
                    bad = 1;
                }
                g[a].push_back(b);
                g[b].push_back(a);
            }
        }else{
            tree[a].push_back(b);
            tree[b].push_back(a);
        }
    }
}

void Init(int N){
    good::Init(N);
    bads::Init(N);
}

void Link(int a, int b){
    good::Link(a, b);
    bads::Link(a, b);
}

int CountCritical(){
    if(bads::cyc) return good::CountCritical();
    else return bads::CountCritical();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 1108 KB Output is correct
3 Correct 5 ms 1180 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 4 ms 1748 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 3 ms 1232 KB Output is correct
9 Correct 4 ms 1500 KB Output is correct
10 Correct 3 ms 1364 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 766 ms 125232 KB Output is correct
2 Correct 1674 ms 159460 KB Output is correct
3 Correct 888 ms 147248 KB Output is correct
4 Correct 2510 ms 240912 KB Output is correct
5 Correct 2428 ms 242016 KB Output is correct
6 Correct 2769 ms 262144 KB Output is correct
7 Correct 808 ms 147136 KB Output is correct
8 Correct 2161 ms 216644 KB Output is correct
9 Correct 1784 ms 237652 KB Output is correct
10 Correct 1549 ms 238048 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 1108 KB Output is correct
3 Correct 5 ms 1180 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 4 ms 1748 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 3 ms 1232 KB Output is correct
9 Correct 4 ms 1500 KB Output is correct
10 Correct 3 ms 1364 KB Output is correct
11 Correct 6 ms 1236 KB Output is correct
12 Correct 19 ms 2620 KB Output is correct
13 Correct 21 ms 2240 KB Output is correct
14 Correct 62 ms 2160 KB Output is correct
15 Correct 89 ms 3028 KB Output is correct
16 Correct 14 ms 2548 KB Output is correct
17 Correct 7 ms 1748 KB Output is correct
18 Correct 7 ms 3284 KB Output is correct
19 Correct 11 ms 2752 KB Output is correct
20 Correct 11 ms 2440 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 1108 KB Output is correct
3 Correct 5 ms 1180 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 4 ms 1748 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 3 ms 1232 KB Output is correct
9 Correct 4 ms 1500 KB Output is correct
10 Correct 3 ms 1364 KB Output is correct
11 Correct 6 ms 1236 KB Output is correct
12 Correct 19 ms 2620 KB Output is correct
13 Correct 21 ms 2240 KB Output is correct
14 Correct 62 ms 2160 KB Output is correct
15 Correct 89 ms 3028 KB Output is correct
16 Correct 14 ms 2548 KB Output is correct
17 Correct 7 ms 1748 KB Output is correct
18 Correct 7 ms 3284 KB Output is correct
19 Correct 11 ms 2752 KB Output is correct
20 Correct 11 ms 2440 KB Output is correct
21 Execution timed out 4059 ms 9228 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 1108 KB Output is correct
3 Correct 5 ms 1180 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 4 ms 1748 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 3 ms 1232 KB Output is correct
9 Correct 4 ms 1500 KB Output is correct
10 Correct 3 ms 1364 KB Output is correct
11 Correct 766 ms 125232 KB Output is correct
12 Correct 1674 ms 159460 KB Output is correct
13 Correct 888 ms 147248 KB Output is correct
14 Correct 2510 ms 240912 KB Output is correct
15 Correct 2428 ms 242016 KB Output is correct
16 Correct 2769 ms 262144 KB Output is correct
17 Correct 808 ms 147136 KB Output is correct
18 Correct 2161 ms 216644 KB Output is correct
19 Correct 1784 ms 237652 KB Output is correct
20 Correct 1549 ms 238048 KB Output is correct
21 Correct 6 ms 1236 KB Output is correct
22 Correct 19 ms 2620 KB Output is correct
23 Correct 21 ms 2240 KB Output is correct
24 Correct 62 ms 2160 KB Output is correct
25 Correct 89 ms 3028 KB Output is correct
26 Correct 14 ms 2548 KB Output is correct
27 Correct 7 ms 1748 KB Output is correct
28 Correct 7 ms 3284 KB Output is correct
29 Correct 11 ms 2752 KB Output is correct
30 Correct 11 ms 2440 KB Output is correct
31 Execution timed out 4059 ms 9228 KB Time limit exceeded
32 Halted 0 ms 0 KB -