oj.uz

Submission #15615

# Submission time Handle Problem Language Result Execution time Memory
15615 2015-07-13T10:29:35 Z gs14004 Parachute rings (IOI12_rings) C++14
0 / 100
 4000 ms 108280 KB 
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
  
int n;
int deg[1000005];
int focus = -1;
bool deadend = 0;
 
int v[4];
int bad[4];

int edg;
int st[1000005], ed[1000005];

struct disj{
    int pa[1000005];
    int deg2[1000005];
    int deg3[1000005];
    int degx[1000005];
    int size[1000005];
    int without;
 
    void init(int n, int w){
        without = w;
        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)]++;
        }
        degx[q]++;
        if(degx[q] == 2){
            deg2[find(q)]++;
        }
        if(degx[q] == 3){
            deg3[find(q)]++;
        }
        p = find(p); q = find(q);
        if(p == q) return;
        pa[q] = p;
        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;
        for(int i=0; i<edg; i++){
            if(st[i] == A || ed[i] == A){
                if(v[2] == -1){
                    if(st[i] != A) v[2] = st[i];
                    else v[2] = ed[i];
                }
                else if(v[3] == -1){
                    if(st[i] != A) v[3] = st[i];
                    else v[3] = ed[i];
                    break;
                }
            }
        }
        for(int i=0; i<4; i++){
            wotree[i].init(n,v[i]);
            for(int j=0; j<edg; j++){
                disj.uni(st[j], ed[j]);
                if(wotree[i].ckBad(st[j])){
                    bad[i] = 1;
                    break;
                }
            }
        }
    }
    st[edg] = A;
    ed[edg] = B;
    edg++;
    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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 5 ms 1012 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 16664 KB Output is correct
2 Correct 3410 ms 88660 KB Output is correct
3 Execution timed out 4029 ms 108280 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 5 ms 1012 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 5 ms 1012 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 5 ms 1012 KB Output isn't correct
3 Halted 0 ms 0 KB -