Submission #50078

#	Time	Username	Problem	Language	Result	Execution time	Memory
50078		top34051	Parachute rings (IOI12_rings)	C++17	0 / 100	1053 ms	62388 KiB

rings

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

const int maxn = 1e6 + 5;

int n;
int bad[maxn], wow;
int deg[maxn], head[maxn];
int mx, mx0, cnt[10], cnt0[10], form, form0;
vector<int> way[maxn];
int path, vis[maxn], pro[maxn];
stack<int> st;
int ans;

void Init(int _n) {
    n = _n;
    for(int i=1;i<=n;i++) head[i] = i;
    cnt[0] = n; ans = n;
}

void update() {
    ans = 0;
    for(int i=1;i<=n;i++) ans += !bad[i];
}

void go(int u, int want) {
    if(u==want) {
        path++;
        return ;
    }
    if(vis[u]) return ;
    vis[u] = 1;
    for(auto v : way[u]) go(v,want);
}

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

int findhead(int x) {
    if(x==head[x]) return x;
    return head[x] = findhead(head[x]);
}

int CountCritical() {
    if(wow) return 0;
    update();
    return ans;
}

void Link(int x, int y) {
    if(wow) return ;

    for(int i=0;i<=4;i++) cnt0[i] = cnt[i];
    form0 = form; mx0 = mx;

    x++; y++;

    cnt[min(4,deg[x])]--; cnt[min(4,deg[y])]--;

    deg[x]++; deg[y]++;
    way[x].push_back(y); way[y].push_back(x);

    cnt[min(4,deg[x])]++; cnt[min(4,deg[y])]++;

    if(cnt[3]+cnt[4]>2) wow = 1;
    if(cnt[4]>1) wow = 1;

    if(wow) return ;

    //update max degree
    mx = max(mx, max(deg[x], deg[y]));

    //circle forming
    if(findhead(x)==findhead(y)) form++;
    head[findhead(x)] = findhead(y);

    if(mx<=2) {
        if(form>1) wow = 1;
        else if(form!=form0) {
            for(int i=1;i<=n;i++) {
                if(findhead(i)!=findhead(x)) bad[i] = 1;
            }
            update();
        }
    }
    else if(mx<=3) {
//        printf("mx = %d : Cnt = %d form = %d\n",mx,cnt[3],form);
        if(cnt[3]==2) {
            if(cnt0[3]!=cnt[3]) {
                int u, v = -1;
                for(int i=1;i<=n;i++) if(deg[i]==3) u = i;
                for(auto t : way[u]) if(deg[t]==3) v = t;
                if(v==-1) wow = 1;
                else {
                    for(int i=1;i<=n;i++) if(i!=u && i!=v) bad[i] = 1;
                    update();
                }
            }
            if(form==2 && form!=form0) {
                int u, v = -1;
                for(int i=1;i<=n;i++) if(deg[i]==3) u = i;
                for(auto t : way[u]) if(deg[t]==3) v = t;
                path = 0;
                memset(vis,0,sizeof(vis));
                go(u,v);
                if(path!=3) wow = 1;
            }
            if(form>2) wow = 1;
        }
        else {
            if(cnt0[3]!=cnt[3]) {
                int u;
                for(int i=1;i<=n;i++) if(deg[i]==3) u = i;
                memset(pro,0,sizeof(pro));
                pro[u] = 1;
                for(auto v : way[u]) pro[v] = 1;
                for(int i=1;i<=n;i++) if(!pro[i]) bad[i] = 1;
                update();
            }
            if(form==1 && form!=form0) {
                memset(vis,0,sizeof(vis));
                memset(pro,0,sizeof(pro));
                while(!st.empty()) st.pop();
                cycle(x,0);
                for(int i=1;i<=n;i++) if(!pro[i]) bad[i] = 1;
                update();
            }
            if(form>1) wow = 1;
        }
    }
    else {
        if(mx!=mx0) {
            for(int i=1;i<=n;i++) if(deg[i]!=4) bad[i] = 1;
            update();
        }
    }
//    printf("\tcurrent critical = %d\n",CountCritical());
}

Compilation message (stderr)

rings.cpp: In function 'void Link(int, int)':
rings.cpp:124:21: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 int u;
                     ^
rings.cpp:112:21: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 int u, v = -1;
                     ^
rings.cpp:102:21: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 int u, v = -1;
                     ^

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