oj.uz

Submission #817683

# Submission time Handle Problem Language Result Execution time Memory
817683 2023-08-09T15:01:03 Z annabeth9680 Parachute rings (IOI12_rings) C++17
0 / 100
 1489 ms 134948 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+20;
int deg[MAXN], ha[MAXN], hb[MAXN],N;
int cur,num,cycnum,cycl;
vector<int> adj[MAXN];
struct dsu{
    int d[MAXN],sz[MAXN];
    void init(int N){
        for(int i = 0;i<N;++i){
            d[i] = i;
            sz[i] = 1;
        }
    }
    int finden(int x){
        return (x == d[x] ? x : d[x] = finden(d[x]));
    }
    int s(int x) {return sz[finden(x)];}
    bool unite(int x, int y){
        x = finden(x); y = finden(y);
        if(x == y) return false;
        d[x] = y; sz[y] += sz[x];
        return true;
    }
}DSU;
struct fall{
    dsu D; int u; int deg[MAXN]; bool ok;
    void init(int v){
        u = v; ok = true;
        fill(deg,deg+N,0); D.init(N);
        for(int i = 0;i<cur;++i){
            if(ha[i] == u || hb[i] == u) continue;
            deg[ha[i]]++; deg[hb[i]]++;
            if(deg[ha[i]] >= 3 || deg[hb[i]] >= 3) ok = false;
            if(!D.unite(ha[i],hb[i])) ok = false;
        }
    }
    void link(){
        int pos = cur-1;
        if(ha[pos] == u || hb[pos] == u) return;
        int a = ha[pos], b = hb[pos];
        deg[a]++; deg[b]++;
        if(deg[a] >= 3 || deg[b] >= 3) ok = false;
        if(!D.unite(a,b)) ok = false;
    }
    bool check(){
        return ok;
    }
}falls[4];
void Init(int n){
    N = n; DSU.init(N);
}
bool good = false;
void Link(int A, int B){
    deg[A]++; deg[B]++; ha[cur] = A; hb[cur] = B; cur++;
    adj[A].push_back(B); adj[B].push_back(A);
    if(good){
        for(int i = 0;i<num;++i) falls[i].link();
        return;
    }
    int u = -1;
    if(deg[A] >= 3) u = A;
    if(deg[B] >= 3) u = B;
    if(u == -1){
        if(!DSU.unite(A,B)){
            cycnum++;
            cycl += DSU.s(A);
        }
        return;
    }
    good = true;
    falls[num++].init(u);
    for(auto v : adj[u]){
        falls[num++].init(v);
    }
}
int CountCritical(){
    if(good){
        int ans = 0;
        for(int i = 0;i<num;++i){
            if(falls[i].check()){
                ans++;
            }
        }
        return ans;
    }
    else{
        if(cycnum == 2) return 0;
        if(cycnum == 1) return cycl;
        return N;
    }
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23852 KB Output is correct
2 Correct 14 ms 24404 KB Output is correct
3 Correct 15 ms 24404 KB Output is correct
4 Correct 14 ms 23812 KB Output is correct
5 Correct 13 ms 23940 KB Output is correct
6 Correct 14 ms 24148 KB Output is correct
7 Correct 13 ms 24164 KB Output is correct
8 Incorrect 13 ms 24088 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 57316 KB Output is correct
2 Correct 935 ms 112772 KB Output is correct
3 Correct 1489 ms 129760 KB Output is correct
4 Correct 929 ms 87972 KB Output is correct
5 Correct 973 ms 88040 KB Output is correct
6 Correct 818 ms 86312 KB Output is correct
7 Correct 1413 ms 128384 KB Output is correct
8 Correct 1028 ms 127892 KB Output is correct
9 Correct 1066 ms 134948 KB Output is correct
10 Incorrect 565 ms 85664 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23852 KB Output is correct
2 Correct 14 ms 24404 KB Output is correct
3 Correct 15 ms 24404 KB Output is correct
4 Correct 14 ms 23812 KB Output is correct
5 Correct 13 ms 23940 KB Output is correct
6 Correct 14 ms 24148 KB Output is correct
7 Correct 13 ms 24164 KB Output is correct
8 Incorrect 13 ms 24088 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23852 KB Output is correct
2 Correct 14 ms 24404 KB Output is correct
3 Correct 15 ms 24404 KB Output is correct
4 Correct 14 ms 23812 KB Output is correct
5 Correct 13 ms 23940 KB Output is correct
6 Correct 14 ms 24148 KB Output is correct
7 Correct 13 ms 24164 KB Output is correct
8 Incorrect 13 ms 24088 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23852 KB Output is correct
2 Correct 14 ms 24404 KB Output is correct
3 Correct 15 ms 24404 KB Output is correct
4 Correct 14 ms 23812 KB Output is correct
5 Correct 13 ms 23940 KB Output is correct
6 Correct 14 ms 24148 KB Output is correct
7 Correct 13 ms 24164 KB Output is correct
8 Incorrect 13 ms 24088 KB Output isn't correct
9 Halted 0 ms 0 KB -