oj.uz

Submission #15607

# Submission time Handle Problem Language Result Execution time Memory
15607 2015-07-13T08:25:13 Z gs14004 Parachute rings (IOI12_rings) C++14
52 / 100
 4000 ms 127748 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
 
vector<int> graph[1000005];
int n;
int deg[1000005];
int focus = -1;
bool deadend = 0;

int v[4];
int bad[4];

struct disj{
    int pa[1000005];
    int deg2[1000005];
    bool deg3[1000005];
    int degx[1000005];
    int size[1000005];
    int without;

    void init(int n, int w){
        without = w;
        memset(degx, 0, sizeof(degx));
        memset(deg2, 0, sizeof(deg2));
        memset(deg3, 0, sizeof(deg3));
        for(int i=0; i<=n; i++) pa[i] = i, size[i] = 1;
    }
 
    int find(int x){
        return pa[x] = (pa[x] == x ? x : find(pa[x]));
    }
 
    void uni(int p, int q){
        if(p == without || q == without) return;
        degx[p]++;
        if(degx[p] == 2){
            deg2[find(p)]++;
        }
        if(degx[p] == 3){
            deg3[find(p)]= 1;
        }
        degx[q]++;
        if(degx[q] == 2){
            deg2[find(q)]++;
        }
        if(degx[q] == 3){
            deg3[find(q)] = 1;
        }
        p = find(p); q = find(q);
        if(p == q) return;
        pa[q] = p; find(q);
        deg2[p] += deg2[q];
        deg3[p] += deg3[q];
        size[p] += size[q];
    }

    bool ckBad(int x){
        x = find(x);
        return (deg3[x] || (deg2[x] == size[x]));
    }
}disj, wotree[4];
 
void Init(int N){
    n = N; 
    memset(v,-1,sizeof(v));
    disj.init(n,-1);
}

void Link(int A, int B){
    deg[A]++, deg[B]++;
    if(deg[A] <= deg[B]){
        swap(A,B);
    }
    if(deg[A] == 3 && v[0] == -1){
        v[0] = A;
        v[1] = B;
        v[2] = graph[A][0];
        v[3] = graph[A][1];
        for(int i=0; i<4; i++){
            wotree[i].init(n,v[i]);
            for(int j=0; j<n; j++){
                for(auto &k : graph[j]){
                    if(j < k) wotree[i].uni(j,k);
                }
            }
            for(int j=0; j<n; j++){
                if(j != v[i] && wotree[i].ckBad(j)){
                    bad[i] = 1;
                    break;
                }
            }
        }
    }
    graph[A].push_back(B);
    graph[B].push_back(A);
    disj.uni(A,B);
    if(v[0] == -1){
        if(disj.ckBad(A)){
            if(focus == -1){
                focus = A;
            }
            else if(disj.find(focus) != disj.find(A)){
                deadend = 1;
            }
        }
    }
    else{
        for(int i=0; i<4; i++){
            wotree[i].uni(A,B);
            if(wotree[i].ckBad(A)){
                bad[i] = 1;
            }
        }
    }
}

 
int CountCritical(){
    if(deadend == 1) return 0;
    if(disj.without != -1) return 1;
    else if(v[0] != -1){
        int cnt = 0;
        for(int i=0; i<4; i++){
            if(!bad[i]) cnt++;
        }
        return cnt;
    }
    else{ 
        if(focus == -1) return n;
        return disj.size[disj.find(focus)];
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 32632 KB Output is correct
2 Correct 58 ms 68392 KB Output is correct
3 Correct 61 ms 68392 KB Output is correct
4 Correct 31 ms 68392 KB Output is correct
5 Correct 32 ms 68392 KB Output is correct
6 Correct 34 ms 68392 KB Output is correct
7 Correct 64 ms 68484 KB Output is correct
8 Correct 32 ms 68484 KB Output is correct
9 Correct 64 ms 68512 KB Output is correct
10 Correct 62 ms 68612 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 68612 KB Output is correct
2 Execution timed out 4042 ms 127748 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 32632 KB Output is correct
2 Correct 58 ms 68392 KB Output is correct
3 Correct 61 ms 68392 KB Output is correct
4 Correct 31 ms 68392 KB Output is correct
5 Correct 32 ms 68392 KB Output is correct
6 Correct 34 ms 68392 KB Output is correct
7 Correct 64 ms 68484 KB Output is correct
8 Correct 32 ms 68484 KB Output is correct
9 Correct 64 ms 68512 KB Output is correct
10 Correct 62 ms 68612 KB Output is correct
11 Correct 59 ms 127748 KB Output is correct
12 Correct 62 ms 127748 KB Output is correct
13 Correct 63 ms 127748 KB Output is correct
14 Correct 62 ms 127748 KB Output is correct
15 Correct 69 ms 127748 KB Output is correct
16 Correct 34 ms 127748 KB Output is correct
17 Correct 62 ms 127748 KB Output is correct
18 Correct 66 ms 127748 KB Output is correct
19 Correct 34 ms 127748 KB Output is correct
20 Correct 65 ms 127748 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 32632 KB Output is correct
2 Correct 58 ms 68392 KB Output is correct
3 Correct 61 ms 68392 KB Output is correct
4 Correct 31 ms 68392 KB Output is correct
5 Correct 32 ms 68392 KB Output is correct
6 Correct 34 ms 68392 KB Output is correct
7 Correct 64 ms 68484 KB Output is correct
8 Correct 32 ms 68484 KB Output is correct
9 Correct 64 ms 68512 KB Output is correct
10 Correct 62 ms 68612 KB Output is correct
11 Correct 59 ms 127748 KB Output is correct
12 Correct 62 ms 127748 KB Output is correct
13 Correct 63 ms 127748 KB Output is correct
14 Correct 62 ms 127748 KB Output is correct
15 Correct 69 ms 127748 KB Output is correct
16 Correct 34 ms 127748 KB Output is correct
17 Correct 62 ms 127748 KB Output is correct
18 Correct 66 ms 127748 KB Output is correct
19 Correct 34 ms 127748 KB Output is correct
20 Correct 65 ms 127748 KB Output is correct
21 Correct 51 ms 127748 KB Output is correct
22 Correct 62 ms 127748 KB Output is correct
23 Correct 74 ms 127748 KB Output is correct
24 Correct 153 ms 127748 KB Output is correct
25 Correct 80 ms 127748 KB Output is correct
26 Correct 153 ms 127748 KB Output is correct
27 Correct 88 ms 127748 KB Output is correct
28 Correct 178 ms 127748 KB Output is correct
29 Correct 123 ms 127748 KB Output is correct
30 Correct 103 ms 127748 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 32632 KB Output is correct
2 Correct 58 ms 68392 KB Output is correct
3 Correct 61 ms 68392 KB Output is correct
4 Correct 31 ms 68392 KB Output is correct
5 Correct 32 ms 68392 KB Output is correct
6 Correct 34 ms 68392 KB Output is correct
7 Correct 64 ms 68484 KB Output is correct
8 Correct 32 ms 68484 KB Output is correct
9 Correct 64 ms 68512 KB Output is correct
10 Correct 62 ms 68612 KB Output is correct
11 Correct 713 ms 68612 KB Output is correct
12 Execution timed out 4042 ms 127748 KB Time limit exceeded
13 Halted 0 ms 0 KB -