Submission #501089

#	Time	Username	Problem	Language	Result	Execution time	Memory
501089		doowey	Parachute rings (IOI12_rings)	C++14	100 / 100	1727 ms	115356 KiB

rings

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)1e6 + 5;

int n;
int par[N];
int deg[N];
vector<int> T[N];

int phase;

void Init(int _n) {
    n = _n;
    phase = 0;
    for(int i = 0 ; i < n; i ++ ){
        par[i] = i;
    }
}

int fin(int u){
    if(par[u] == u) return u;
    return par[u]=fin(par[u]);
}

struct graph{
    int P[N];
    int D[N]; // all deg <= 2 + no cycles
    bool valid;
    int disable;
    void init(){
        for(int i = 0; i < n; i ++ ){
            P[i] = i;
        }
        valid = true;
    }
    int finn(int x){
        if(P[x] == x) return x;
        return P[x]=finn(P[x]);
    }
    void add_edge(int u, int v){
        if(u == disable || v == disable) return;
        D[u] ++ ;
        D[v] ++ ;
        if(D[u] >= 3 || D[v] >= 3) valid = false;
        u = finn(u);
        v = finn(v);
        if(u == v) valid = false;
        else P[u] = v;
    }
};

vector<pii> E;
graph Q[4];

int cycle;

void construct(int u){
    for(int i = 0 ; i < 4; i ++ ){
        Q[i].init();
        if(i < 3) Q[i].disable = T[u][i];
        else Q[i].disable = u;
        for(auto x : E){
            Q[i].add_edge(x.fi, x.se);
        }
    }
}

void dfs(int u, int par, int leng, int target){
    if(u == target){
        cycle = leng;
    }
    for(auto x : T[u]){
        if(x == par){
            continue;
        }
        dfs(x, u, leng + 1, target);
    }
}

void Link(int a, int b) {
    if(phase == -1) return;
    E.push_back(mp(a, b));
    deg[a] ++ ;
    deg[b] ++ ;
    T[a].push_back(b);
    T[b].push_back(a);
    if(phase == 0){
        if(fin(a) == fin(b)){
            phase = 1;
            T[a].pop_back();
            T[b].pop_back();

            dfs(a, -1, 1, b);

            T[a].push_back(b);
            T[b].push_back(a);
        }
        else{
            par[fin(a)] = fin(b);
        }

        if(deg[a] == 3){
            construct(a);
            phase = 2;
            return;
        }
        if(deg[b] == 3){
            construct(b);
            phase = 2;
            return;
        }
    }
    else if(phase == 1){
        if(deg[a] == 3){
            construct(a);
            phase = 2;
            return;
        }
        if(deg[b] == 3){
            construct(b);
            phase = 2;
            return;
        }
        if(fin(a) == fin(b)){
            phase = -1;
            return;
        }
        else{
            par[fin(a)] = fin(b);
        }
    }
    else{
        for(int i = 0 ; i < 4; i ++ ){
            Q[i].add_edge(a, b);
        }
    }
}


int CountCritical() {
    if(phase == -1){
        return 0;
    }
    if(phase == 0){
        return n;
    }
    if(phase == 1){
        return cycle;
    }
    if(phase == 2){
        return (Q[0].valid + Q[1].valid + Q[2].valid + Q[3].valid);
    }
}

Compilation message (stderr)

rings.cpp: In function 'int CountCritical()':
rings.cpp:162:1: warning: control reaches end of non-void function [-Wreturn-type]
  162 | }
      | ^

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