Submission #1013356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013356		Ludissey	Parachute rings (IOI12_rings)	C++14	0 / 100	729 ms	141588 KiB

rings

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
int n;
bool hasloop=false;
vector<vector<int>> neigh;
vector<int> visited;
vector<int> parent;
vector<int> pr;
vector<int> sz;
vector<int> crit;
vector<int> incycle;
int timer=0;
int exceptation=-1;
bool cycl=0;
int cc=0;
int c=0;
int upds=0;

int getParent(int a) { return parent[a]==a ? a : parent[a]=getParent(parent[a]); }

void unite(int a, int b){
    a=getParent(a); b=getParent(b);
    if(a==b) return;
    if(sz[b]>sz[a]) swap(a,b);
    sz[a]+=sz[b];
    parent[a]=b;
}

void detect_cycle(int x, int p) {
    if(visited[x]==2) return;
    if (visited[x] == 1) {
        vector<int> v;
        incycle.push_back(x);
        int cr=pr[x];
        while (cr!=x) {
            incycle.push_back(cr);
            cr=pr[cr];
        } 
        return;
    }
    pr[x]=p;
    visited[x]=1;
    for (int to : neigh[x]) {
        if (to==p) continue;
        detect_cycle(to,x);
    }
    visited[x]=2;
}

void Init(signed N_) {
    n = N_;
    parent.resize(n);
    visited.resize(n,0);
    neigh.resize(n);
    cc=0;
    sz.resize(n,1);
    pr.resize(n,-1);
    crit.resize(n,0);
    upds=0;
    for (int i = 0; i < n; i++) parent[i]=i;
}


void case1(int A, int B){ //two vertex of different sets O(1);
    unite(A,B);
    if(sz(neigh[A])==3){
        crit[neigh[A][0]]++;
        crit[neigh[A][1]]++;
        crit[neigh[A][2]]++;
        crit[A]++;
        upds++;
    }else if(sz(neigh[A])>3){
        crit[A]++;
        upds++;
    }
    if(sz(neigh[B])==3){
        crit[neigh[B][0]]++;
        crit[neigh[B][1]]++;
        crit[neigh[B][2]]++;
        crit[B]++;
        upds++;
    }else if(sz(neigh[B])>3){
        crit[B]++;
        upds++;
    }
}
void case2(int A, int B){ //two vertex of same sets !! NO CYCLE !! O(N+M)
    detect_cycle(A,B);
    cycl=1;
    for (int i = 0; i < sz(incycle); i++) crit[incycle[i]]++;
    upds++;
    case1(A,B);
}
void case3(int A, int B){ //two vertex of same sets !! CYCLE !! O(1)
    if(sz(neigh[A])==3||sz(neigh[B])==3){
        crit[A]++;
        crit[B]++;
        upds++;
    }
    if(sz(neigh[A])>3){
        crit[A]++;
        upds++;
    }
    if(sz(neigh[B])>3){
        crit[B]++;
        upds++;
    }
}
void Link(signed A, signed B) {
    neigh[A].push_back(B);
    neigh[B].push_back(A);
    if(getParent(A)==getParent(B)){
        if(cycl) case3(A,B);
        else case2(A,B);
    }else{
        case1(A,B);
    }
}

signed CountCritical() {
    c=0;
    for (int i = 0; i < n; i++) if(crit[i]==upds) c++;
    return c;
}

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