Submission #828195

#	Time	Username	Problem	Language	Result	Execution time	Memory
828195		jlallas384	Parachute rings (IOI12_rings)	C++17	38 / 100	4073 ms	152900 KiB

rings

    #include <bits/stdc++.h>
    using namespace std;
     
     
     
    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 cyc = 0;
     
    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;
    }
     
    vector<pair<int,int>> eds;
     
     
    void Link(int a, int b){
        int res = ds.unite(a, b);
        deg[a]++, deg[b]++;
        g[a].push_back(b);
        g[b].push_back(a);
        eds.emplace_back(a, b);
        proc(a), proc(b);
        cyc += !res;
    }
     
    int CountCritical(){    
        if(cyc == 0) return ans.size();
        int fans = 0;
        set<int> nans;
        for(int x: ans){
            ufds f(n);
            int can = 1;
            for(auto [u, v]: eds) if(u != x && v != x){
                if(!f.unite(u, v)) can = 0;
            }
            fans += can;
            if(can) nans.insert(x);
        }
        ans = nans;
        return fans;
    }

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