oj.uz

Submission #799297

# Submission time Handle Problem Language Result Execution time Memory
799297 2023-07-31T12:08:31 Z jlallas384 Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 90200 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;
    }
     
    int dfs2(int v, vector<int> &vis, int p){
        vis[v] = 2;
        for(int u: g[v]){
            if(!vis[u]){
                if(dfs2(u, vis, v)) return 1;
            }
            else if(vis[u] == 2 && u != p){
                return 1;
            }
        }
        return 0;
    }
    int cancer = -1;
    int CountCritical(){    
        if(bad) return 0;
        if(ans.size() == 0) return 0;
        int tot = 0;
        set<int> gds;
        int cnts = 0;
        for(int i = 0; i < n; i++){
            cnts += deg[i] >= 3;
        }
        for(int v: ans){
            int ok = 1;
            int t = cnts - (deg[v] >= 3);
            if(deg[v] != 2){
                vector<int> vis(n);
                vis[v] = 1;
                for(int u: g[v]){
                    t -= (deg[u] == 3);
                }
                for(int i = 0; i < n; i++){
                    if(!vis[i] && dfs2(i, vis, -1)){
                        ok = 0;
                    }
                }
            }
            ok &= (t == 0 || deg[v] == 2);
            tot += ok;
            if(ok) gds.insert(v);
        }
        if(tot == 0) bad = 1;
        cancer = tot;
        assert(gds == ans);
        assert(tot == ans.size());
        if(bad) return 0;
        else if(!cyc) return ans.size();
        return tot;
    }
     
     
     
     
     
     
    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() > 2) bad = 1;
                return;
            }
        }else{
            tree[a].push_back(b);
            tree[b].push_back(a);
        }
    }

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from rings.cpp:1:
rings.cpp: In function 'int CountCritical()':
rings.cpp:119:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         assert(tot == ans.size());
      |                ~~~~^~~~~~~~~~~~~

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 852 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 4 ms 1408 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 2 ms 944 KB Output is correct
9 Correct 3 ms 1108 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4067 ms 90200 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 4 ms 1408 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 2 ms 944 KB Output is correct
9 Correct 3 ms 1108 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Incorrect 2444 ms 1420 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 4 ms 1408 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 2 ms 944 KB Output is correct
9 Correct 3 ms 1108 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Incorrect 2444 ms 1420 KB Output isn't correct
12 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 852 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 4 ms 1408 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 2 ms 944 KB Output is correct
9 Correct 3 ms 1108 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Execution timed out 4067 ms 90200 KB Time limit exceeded
12 Halted 0 ms 0 KB -