Submission #248554

#	Time	Username	Problem	Language	Result	Execution time	Memory
248554		alexandra_udristoiu	낙하산 고리들 (IOI12_rings)	C++14	52 / 100	4030 ms	144112 KiB

rings

#include<vector>
using namespace std;
const int dim = 1000005;
int n, nr3, nr4, m, num, nrcomp, nrcic, np;
int r[dim], g[dim], viz[dim], t[dim], frst[dim], cic[dim], rp[dim], r2[20][dim], nrc[20], nnod[20];
pair<int, int> w[dim];
vector<int> v[dim], g3, g4;
int rad(int x){
    int aux, y = x;
    while(r[x] > 0){
        x = r[x];
    }
    while(r[y] > 0){
        aux = r[y];
        r[y] = x;
        y = aux;
    }
    return x;
}
void uneste(int i, int x, int y){
    if(x == nnod[i] || y == nnod[i]){
        return;
    }
    int ax = x, ay = y, aux;
    while(r2[i][x] >= 0){
        x = r2[i][x];
    }
    while(r2[i][y] >= 0){
        y = r2[i][y];
    }
    while(r2[i][ax] > 0){
        aux = r2[i][ax];
        r2[i][ax] = x;
        ax = aux;
    }
    while(r2[i][ay] > 0){
        aux = r2[i][ay];
        r2[i][ay] = y;
        ay = aux;
    }
    if(x != y){
        nrc[i]++;
        if(r2[i][x] > r2[i][y]){
            r2[i][x] += r2[i][y];
            r2[i][y] = x;
        }
        else{
            r2[i][y] += r2[i][x];
            r2[i][x] = y;
        }
    }
}
void update(int nod){
    if(rp[nod] == 0 && g3.size() < 4 && g4.size() == 0){
        np++;
        rp[nod] = np;
        nnod[np] = nod;
        for(int i = 1; i <= m; i++){
            uneste(np, w[i].first, w[i].second);
        }
    }
}
void upd(int nod){
    if(g[nod] == 4){
        nr3--;
        nr4++;
        g4.push_back(nod);
    }
    else if(g[nod] == 3){
        nr3++;
        g3.push_back(nod);
        update(nod);
        for(int i = 0; i < v[nod].size(); i++){
            frst[ v[nod][i] ] = nod;
            update(v[nod][i]);
        }
    }
}
int verif(int nod){
    if(m - g[nod] != nrc[ rp[nod] ] ){
        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;
    for(int i = 0; i < n; i++){
        r[i] = -1;
        for(int ii = 1; ii <= 18; ii++){
            r2[ii][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;
        update(y);
    }
    if(g[y] == 3){
        frst[x] = y;
        update(x);
    }
    upd(x);
    upd(y);
    r1 = rad(x);
    r2 = rad(y);
    m++;
    if(r1 != r2){
        if(r[r1] < r[r2]){
            r[r1] += r[r2];
            r[r2] = r1;
            cic[r1] |= cic[r2];
        }
        else{
            r[r2] += r[r1];
            r[r1] = r2;
            cic[r2] |= cic[r1];
            swap(r1, r2);
        }
    }
    else{
        nrcic++;
        if(nrcic == 1 && g3.size() == 0){
            t[x] = -1;
            dfs(x, -1);
            nod = y;
            while(nod != -1){
                viz[nod] = 1;
                nod = t[nod];
                num++;
            }
        }
        if(cic[r1] == 0){
            nrcomp++;
            cic[r1] = 1;
        }
    }
    v[x].push_back(y);
    v[y].push_back(x);
    w[m] = make_pair(x, y);
    for(int i = 1; i <= np; i++){
        uneste(i, x, y);
    }
}

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(nrcomp > 1){
        return 0;
    }
    if(nrcomp == 1){
        return num;
    }
    return n;
}

Compilation message (stderr)

rings.cpp: In function 'void upd(int)':
rings.cpp:73: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:87:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); i++){
                    ~~^~~~~~~~~~~~~~~
rings.cpp:83:9: warning: unused variable 'i' [-Wunused-variable]
     int i, n3 = 0;
         ^
rings.cpp: In function 'void dfs(int, int)':
rings.cpp:110: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:186: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: 0 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 0 / 31