Submission #828094

#	Time	Username	Problem	Language	Result	Execution time	Memory
828094		jlallas384	Parachute rings (IOI12_rings)	C++17	55 / 100	4059 ms	262144 KiB

rings

#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 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31