Submission #1013439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013439		Ludissey	Parachute rings (IOI12_rings)	C++14	20 / 100	3395 ms	262144 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;
vector<int> iscycle;
vector<int> orig;
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;
        iscycle[x]=true;
        incycle.push_back(x);
        int cr=pr[x];
        while (cr!=x) {
            incycle.push_back(cr);
            iscycle[cr]=true;
            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 get_origin(int x, int p,int og) {
    orig[x]=og;
    for (int to : neigh[x]) {
        if (to==p||iscycle[to]) continue;
        get_origin(to,x,orig[x]);
    }
}

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

void update_crit(int X){
    if(sz(neigh[X])==3){
        crit[neigh[X][0]]++;
        crit[neigh[X][1]]++;
        crit[neigh[X][2]]++;
        crit[X]++;
        upds++;
    }else if(sz(neigh[X])>3){
        crit[X]++;
        upds++;
    }
}

void case1(int A, int B){ //two vertex of different sets O(1);
    unite(A,B);
    if(orig[A]>=0&&orig[B]<0) get_origin(B,A,orig[A]);
    else if(orig[B]>=0&&orig[A]<0) get_origin(A,B,orig[B]);
    update_crit(A);
    update_crit(B);
}
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++;
    visited.clear();
    visited.resize(n,0);
    for (int i = 0; i < sz(incycle); i++) get_origin(incycle[i],-1,incycle[i]);
    case1(A,B);
}
void case3(int A, int B){ //two vertex of same sets !! CYCLE !! O(1)
    //cerr << "case 3";
    if(orig[A]<0||orig[B]<0) { upds++; return; }
    crit[orig[A]]++;
    if(orig[A]!=orig[B]) crit[orig[B]]++;
    upds++;
    update_crit(A);
    update_crit(B);
    update_crit(orig[A]);
    update_crit(orig[B]);
}
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: 20 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31