oj.uz

답안 #828195

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
828195 2023-08-17T06:33:46 Z jlallas384 낙하산 고리들 (IOI12_rings) C++17
38 / 100
 4000 ms 152900 KB 
    #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.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 44 ms 724 KB Output is correct
6 Correct 129 ms 1220 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 103 ms 956 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 3 ms 980 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 326 ms 75572 KB Output is correct
2 Correct 694 ms 102960 KB Output is correct
3 Correct 862 ms 106512 KB Output is correct
4 Execution timed out 4073 ms 152900 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 44 ms 724 KB Output is correct
6 Correct 129 ms 1220 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 103 ms 956 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 759 ms 1884 KB Output is correct
13 Correct 6 ms 1620 KB Output is correct
14 Correct 5 ms 1364 KB Output is correct
15 Correct 8 ms 2564 KB Output is correct
16 Correct 772 ms 1944 KB Output is correct
17 Correct 4 ms 1492 KB Output is correct
18 Correct 6 ms 2592 KB Output is correct
19 Correct 1052 ms 2124 KB Output is correct
20 Correct 4 ms 1876 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 44 ms 724 KB Output is correct
6 Correct 129 ms 1220 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 103 ms 956 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 759 ms 1884 KB Output is correct
13 Correct 6 ms 1620 KB Output is correct
14 Correct 5 ms 1364 KB Output is correct
15 Correct 8 ms 2564 KB Output is correct
16 Correct 772 ms 1944 KB Output is correct
17 Correct 4 ms 1492 KB Output is correct
18 Correct 6 ms 2592 KB Output is correct
19 Correct 1052 ms 2124 KB Output is correct
20 Correct 4 ms 1876 KB Output is correct
21 Correct 21 ms 7120 KB Output is correct
22 Correct 46 ms 11276 KB Output is correct
23 Correct 43 ms 14096 KB Output is correct
24 Execution timed out 4062 ms 10812 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 44 ms 724 KB Output is correct
6 Correct 129 ms 1220 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 103 ms 956 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 326 ms 75572 KB Output is correct
12 Correct 694 ms 102960 KB Output is correct
13 Correct 862 ms 106512 KB Output is correct
14 Execution timed out 4073 ms 152900 KB Time limit exceeded
15 Halted 0 ms 0 KB -