oj.uz

Submission #15601

# Submission time Handle Problem Language Result Execution time Memory
15601 2015-07-13T07:53:59 Z gs14004 Parachute rings (IOI12_rings) C++14
0 / 100
 4000 ms 209020 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][5];
    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] <= 4){
            degcnt[find(p)][degx[p]-1]--;
            degcnt[find(p)][degx[p]]++;
        }
        degx[q]++;
        if(degx[q] <= 4){
            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<5; i++){
            degcnt[p][i] += degcnt[q][i];
        }
        size[p] += size[q];
    }

    bool ckBad(int x){
        x = find(x);
        return (degcnt[x][4] || degcnt[x][3] || (degcnt[x][2] && !degcnt[x][1]));
    }
}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(wotree[i].ckBad(j)){
                    bad[i] = 1;
                }
            }
        }
    }
    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[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:105: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:120:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<v.size(); i++){
                      ~^~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 47228 KB Output is correct
2 Correct 111 ms 141684 KB Output is correct
3 Correct 114 ms 141740 KB Output is correct
4 Incorrect 40 ms 141740 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 141740 KB Output is correct
2 Correct 3946 ms 200960 KB Output is correct
3 Execution timed out 4022 ms 209020 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 47228 KB Output is correct
2 Correct 111 ms 141684 KB Output is correct
3 Correct 114 ms 141740 KB Output is correct
4 Incorrect 40 ms 141740 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 47228 KB Output is correct
2 Correct 111 ms 141684 KB Output is correct
3 Correct 114 ms 141740 KB Output is correct
4 Incorrect 40 ms 141740 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 47228 KB Output is correct
2 Correct 111 ms 141684 KB Output is correct
3 Correct 114 ms 141740 KB Output is correct
4 Incorrect 40 ms 141740 KB Output isn't correct
5 Halted 0 ms 0 KB -