oj.uz

Submission #799318

# Submission time Handle Problem Language Result Execution time Memory
799318 2023-07-31T12:36:09 Z jlallas384 Parachute rings (IOI12_rings) C++17
37 / 100
 1987 ms 199872 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 dfs4(int v, int p, vector<int> &vis){
    vis[v] = 2;
    for(int u: g[v]){
        if(!vis[u] && 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) || cyc == 0);
            }
        }
        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);

    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 4 ms 976 KB Output is correct
3 Correct 4 ms 980 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 4 ms 1364 KB Output is correct
7 Correct 2 ms 816 KB Output is correct
8 Correct 3 ms 980 KB Output is correct
9 Correct 3 ms 1236 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 88572 KB Output is correct
2 Correct 1382 ms 113932 KB Output is correct
3 Correct 432 ms 109332 KB Output is correct
4 Correct 1470 ms 170964 KB Output is correct
5 Correct 1467 ms 171780 KB Output is correct
6 Correct 1873 ms 199872 KB Output is correct
7 Correct 389 ms 108524 KB Output is correct
8 Correct 1987 ms 153592 KB Output is correct
9 Correct 1482 ms 168076 KB Output is correct
10 Correct 1072 ms 166644 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 4 ms 976 KB Output is correct
3 Correct 4 ms 980 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 4 ms 1364 KB Output is correct
7 Correct 2 ms 816 KB Output is correct
8 Correct 3 ms 980 KB Output is correct
9 Correct 3 ms 1236 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Runtime error 5 ms 1876 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 4 ms 976 KB Output is correct
3 Correct 4 ms 980 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 4 ms 1364 KB Output is correct
7 Correct 2 ms 816 KB Output is correct
8 Correct 3 ms 980 KB Output is correct
9 Correct 3 ms 1236 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Runtime error 5 ms 1876 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 4 ms 976 KB Output is correct
3 Correct 4 ms 980 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 4 ms 1364 KB Output is correct
7 Correct 2 ms 816 KB Output is correct
8 Correct 3 ms 980 KB Output is correct
9 Correct 3 ms 1236 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Correct 556 ms 88572 KB Output is correct
12 Correct 1382 ms 113932 KB Output is correct
13 Correct 432 ms 109332 KB Output is correct
14 Correct 1470 ms 170964 KB Output is correct
15 Correct 1467 ms 171780 KB Output is correct
16 Correct 1873 ms 199872 KB Output is correct
17 Correct 389 ms 108524 KB Output is correct
18 Correct 1987 ms 153592 KB Output is correct
19 Correct 1482 ms 168076 KB Output is correct
20 Correct 1072 ms 166644 KB Output is correct
21 Runtime error 5 ms 1876 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -