Submission #50109

#	Time	Username	Problem	Language	Result	Execution time	Memory
50109		top34051	Parachute rings (IOI12_rings)	C++17	55 / 100	4030 ms	94848 KiB

rings

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 5;

int n;
vector<int> way[maxn];
vector<int> deg[10];
int cut[maxn];
int sz, cy, vis[maxn];
stack<int> st;
int ok[maxn];

void Init(int _n) {
    n = _n;
}

void cycle(int u, int last, int ban) {
    if(vis[u]) {
        while(!st.empty()) {
            int v = st.top(); st.pop();
            sz++;
            if(v==u) break;
        }
        cy++;
        return ;
    }
    vis[u] = 1; st.push(u);
    for(auto v : way[u]) {
        if(v!=ban && v!=last && vis[v]<2) {
            cycle(v,u,ban);
        }
    }
    vis[u] = 2;
    if(!st.empty()) st.pop();
}

int check(int u) {
    memset(cut,0,sizeof(cut));
    for(auto v : way[u]) cut[v]++;
    for(int i=1;i<=n;i++) if(i!=u && way[i].size()-cut[i]>2) return 0;
    sz = cy = 0; memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++) if(i!=u && !vis[i]) cycle(i,0,u);
    return cy==0;
}

int CountCritical() {
    for(int i=0;i<=4;i++) deg[i].clear();
    for(int x=1;x<=n;x++) deg[min(4,(int)way[x].size())].push_back(x);
    if(deg[4].size()) {
        memset(ok,0,sizeof(ok));
        if(deg[4].size()<=1) {
            for(auto u : deg[4]) if(!ok[u] && check(u)) ok[u] = 1;
        }
        int res = 0;
        for(int x=1;x<=n;x++) res += ok[x];
        return res;
    }
    if(deg[3].size()) {
        memset(ok,0,sizeof(ok));
        if(deg[3].size()<=3) {
            for(auto u : deg[3]) {
                if(!ok[u] && check(u)) ok[u] = 1;
                for(auto v : way[u]) if(!ok[v] && check(v)) ok[v] = 1;
            }
        }
        int res = 0;
        for(int x=1;x<=n;x++) res += ok[x];
        return res;
    }
    sz = cy = 0; memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++) if(!vis[i]) cycle(i,0,0);
    if(cy==0) return n;
    else if(cy==1) return sz;
    else return 0;
}

void Link(int x, int y) {
    x++; y++;
    way[x].push_back(y); way[y].push_back(x);
}

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