Submission #246556

#	Time	Username	Problem	Language	Result	Execution time	Memory
246556		alexandra_udristoiu	Parachute rings (IOI12_rings)	C++14	37 / 100	1162 ms	105612 KiB

rings

#include<vector>
using namespace std;
const int dim = 1000005;
int n, nr3, nr4, m, num, nrcomp, nrcic;
int r[dim], g[dim], viz[dim], t[dim], frst[dim];
vector<int> v[dim], g3, g4;
int rad(int x){
    while(r[x] > 0){
        x = r[x];
    }
    return x;
}
void upd(int nod){
    if(g[nod] == 4){
        nr3--;
        nr4++;
        g4.push_back(nod);
    }
    else if(g[nod] == 3){
        nr3++;
        g3.push_back(nod);
        for(int i = 0; i < v[nod].size(); i++){
            frst[ v[nod][i] ] = nod;
        }
    }
}
int verif(int nod){
    if(nrcic > 1){
        return 0;
    }
    if(nrcic == 1 && viz[nod] == 0){
        return 0;
    }
    int i, n3 = 0;
    if(g[nod] == 3){
        n3++;
    }
    for(int i = 0; i < v[nod].size(); i++){
        if(g[ v[nod][i] ] == 3){
            n3++;
        }
    }
    if(n3 != nr3){
        return 0;
    }
    return 1;
}

void Init(int N) {
    n = N;
    nrcomp = n;
    for(int i = 0; i < n; i++){
        r[i] = -1;
    }
}

static void dfs(int nod, int tt){
    t[nod] = tt;
    for(int i = 0; i < v[nod].size(); i++){
        if(v[nod][i] != tt){
            dfs(v[nod][i], nod);
        }
    }
}
void Link(int x, int y) {
    int r1, r2, nod;
    g[x]++;
    g[y]++;
    if(g[x] == 3){
        frst[y] = x;
    }
    if(g[y] == 3){
        frst[x] = y;
    }
    upd(x);
    upd(y);
    r1 = rad(x);
    r2 = rad(y);
    m++;
    if(r1 != r2){
        nrcomp--;
        if(r[r1] < r[r2]){
            r[r1] += r[r2];
            r[r2] = r1;
        }
        else{
            r[r2] += r[r1];
            r[r1] = r2;
        }
    }
    else{
        nrcic++;
        if(nrcic == 1){
            t[x] = -1;
            dfs(x, -1);
            nod = y;
            while(nod != -1){
                viz[nod] = 1;
                nod = t[nod];
                num++;
            }
        }
    }
    v[x].push_back(y);
    v[y].push_back(x);
}

int CountCritical() {
    if(nr4 > 1){
        return 0;
    }
    if(nr4 == 1){
        return verif(g4[0]);
    }
    if(nr3 > 3){
        return 0;
    }
    if(nr3 != 0){
        int nr = 0;
        for(int i = 0; i < nr3; i++){
            nr += verif(g3[i]);
            int nod = g3[i];
            for(int j = 0; j < v[nod].size(); j++){
                if(frst[ v[nod][j] ] == nod && g[ v[nod][j] ] < 3){
                    nr += verif(v[nod][j]);
                }
            }
        }
        return nr;
    }
    if(nrcic > 1){
        return 0;
    }
    if(nrcic == 1){
        return num;
    }
    return n;
}

Compilation message (stderr)

rings.cpp: In function 'void upd(int)':
rings.cpp:22:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < v[nod].size(); i++){
                        ~~^~~~~~~~~~~~~~~
rings.cpp: In function 'int verif(int)':
rings.cpp:38:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); i++){
                    ~~^~~~~~~~~~~~~~~
rings.cpp:34:9: warning: unused variable 'i' [-Wunused-variable]
     int i, n3 = 0;
         ^
rings.cpp: In function 'void dfs(int, int)':
rings.cpp:59:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); i++){
                    ~~^~~~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:123:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < v[nod].size(); j++){
                            ~~^~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31