oj.uz

Submission #15604

# Submission time Handle Problem Language Result Execution time Memory
15604 2015-07-13T08:09:53 Z gs14004 Parachute rings (IOI12_rings) C++14
52 / 100
 4000 ms 189564 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;

vector<int> v;
int bad[4];

struct disj{
    int pa[1000005];
    int degcnt[1000005][4];
    int degx[1000005];
    int size[1000005];
    int without;

    void init(int n, int w){
        without = w;
        memset(degcnt, 0, sizeof(degcnt));
        memset(degx, 0, sizeof(degx));
        for(int i=0; i<=n; i++) pa[i] = i, degcnt[i][0] = 1, 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] <= 3){
            degcnt[find(p)][degx[p]-1]--;
            degcnt[find(p)][degx[p]]++;
        }
        degx[q]++;
        if(degx[q] <= 3){
            degcnt[find(q)][degx[q]-1]--;
            degcnt[find(q)][degx[q]]++;
        }
        p = find(p); q = find(q);
        if(p == q) return;
        pa[q] = p; find(q);
        for(int i=0; i<4; i++){
            degcnt[p][i] += degcnt[q][i];
        }
        size[p] += size[q];
    }

    bool ckBad(int x){
        x = find(x);
        return (degcnt[x][3] || (degcnt[x][2] == size[x]));
    }
}disj, wotree[4];
 
void Init(int N){
    n = N; 
    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.empty()){
        v.push_back(A);
        v.push_back(B);
        for(auto &i : graph[A]){
            v.push_back(i);
        }
        for(int i=0; i<v.size(); 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.empty()){
        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<v.size(); 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.empty()){
        int cnt = 0;
        for(int i=0; i<v.size(); i++){
            if(!bad[i]) cnt++;
        }
        return cnt;
    }
    else{ 
        if(focus == -1) return n;
        return disj.size[disj.find(focus)];
    }
}

Compilation message

rings.cpp: In function 'void Link(int, int)':
rings.cpp:77:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<v.size(); i++){
                      ~^~~~~~~~~
rings.cpp:106:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<v.size(); i++){
                      ~^~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:121:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<v.size(); i++){
                      ~^~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 43384 KB Output is correct
2 Correct 96 ms 122164 KB Output is correct
3 Correct 103 ms 122164 KB Output is correct
4 Correct 39 ms 122164 KB Output is correct
5 Correct 41 ms 122164 KB Output is correct
6 Correct 40 ms 122164 KB Output is correct
7 Correct 96 ms 122216 KB Output is correct
8 Correct 40 ms 122216 KB Output is correct
9 Correct 98 ms 122348 KB Output is correct
10 Correct 98 ms 122348 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 633 ms 122348 KB Output is correct
2 Correct 3989 ms 181656 KB Output is correct
3 Execution timed out 4030 ms 189564 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 43384 KB Output is correct
2 Correct 96 ms 122164 KB Output is correct
3 Correct 103 ms 122164 KB Output is correct
4 Correct 39 ms 122164 KB Output is correct
5 Correct 41 ms 122164 KB Output is correct
6 Correct 40 ms 122164 KB Output is correct
7 Correct 96 ms 122216 KB Output is correct
8 Correct 40 ms 122216 KB Output is correct
9 Correct 98 ms 122348 KB Output is correct
10 Correct 98 ms 122348 KB Output is correct
11 Correct 106 ms 189564 KB Output is correct
12 Correct 109 ms 189564 KB Output is correct
13 Correct 104 ms 189564 KB Output is correct
14 Correct 98 ms 189564 KB Output is correct
15 Correct 100 ms 189564 KB Output is correct
16 Correct 42 ms 189564 KB Output is correct
17 Correct 106 ms 189564 KB Output is correct
18 Correct 115 ms 189564 KB Output is correct
19 Correct 43 ms 189564 KB Output is correct
20 Correct 109 ms 189564 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 43384 KB Output is correct
2 Correct 96 ms 122164 KB Output is correct
3 Correct 103 ms 122164 KB Output is correct
4 Correct 39 ms 122164 KB Output is correct
5 Correct 41 ms 122164 KB Output is correct
6 Correct 40 ms 122164 KB Output is correct
7 Correct 96 ms 122216 KB Output is correct
8 Correct 40 ms 122216 KB Output is correct
9 Correct 98 ms 122348 KB Output is correct
10 Correct 98 ms 122348 KB Output is correct
11 Correct 106 ms 189564 KB Output is correct
12 Correct 109 ms 189564 KB Output is correct
13 Correct 104 ms 189564 KB Output is correct
14 Correct 98 ms 189564 KB Output is correct
15 Correct 100 ms 189564 KB Output is correct
16 Correct 42 ms 189564 KB Output is correct
17 Correct 106 ms 189564 KB Output is correct
18 Correct 115 ms 189564 KB Output is correct
19 Correct 43 ms 189564 KB Output is correct
20 Correct 109 ms 189564 KB Output is correct
21 Correct 60 ms 189564 KB Output is correct
22 Correct 76 ms 189564 KB Output is correct
23 Correct 94 ms 189564 KB Output is correct
24 Correct 235 ms 189564 KB Output is correct
25 Correct 127 ms 189564 KB Output is correct
26 Correct 214 ms 189564 KB Output is correct
27 Correct 95 ms 189564 KB Output is correct
28 Correct 260 ms 189564 KB Output is correct
29 Correct 196 ms 189564 KB Output is correct
30 Correct 123 ms 189564 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 43384 KB Output is correct
2 Correct 96 ms 122164 KB Output is correct
3 Correct 103 ms 122164 KB Output is correct
4 Correct 39 ms 122164 KB Output is correct
5 Correct 41 ms 122164 KB Output is correct
6 Correct 40 ms 122164 KB Output is correct
7 Correct 96 ms 122216 KB Output is correct
8 Correct 40 ms 122216 KB Output is correct
9 Correct 98 ms 122348 KB Output is correct
10 Correct 98 ms 122348 KB Output is correct
11 Correct 633 ms 122348 KB Output is correct
12 Correct 3989 ms 181656 KB Output is correct
13 Execution timed out 4030 ms 189564 KB Time limit exceeded
14 Halted 0 ms 0 KB -