Submission #1077042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077042		ArthuroWich	Parachute rings (IOI12_rings)	C++17	38 / 100	4059 ms	119524 KiB

rings

#include<bits/stdc++.h>
using namespace std;
vector<int> adj[1000005];
int n, vis[1000005], p[1000005], s[1000005], timer = 0;
bool f = 1;
int find(int x) {
    if (p[x] == x) {
        return x;
    }
    p[x] = find(p[x]);
    return p[x];
}
void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) {
        return;
    }
    if (s[b] > s[a]) {
        swap(a, b);
    }
    s[a] += s[b];
    p[b] = a;
}
set<int> st;
void Init(int N_) {
    n = N_;
    for (int i = 0; i < n; i++) {
        st.insert(i);
        p[i] = i;
        s[i] = 1;
    }
}
void dfs(int i, int p, int s) {
    if (vis[i] == timer) {
        f = 0;
        return;
    }
    vis[i] = timer;
    for (int j : adj[i]) {
        if (j == p || j == s) {
            continue;
        }
        dfs(j, i, s);
    }
}
int calc(int a) {
    timer++;
    vector<int> co(n, 0);
    for (int j : adj[a]) {
        co[j]++;
    }
    f = 1;
    for (int i = 0; i < n; i++) {
        if (i != a && adj[i].size()-co[i] > 2) {
            f = 0;
            break;
        }
        if (vis[i] == timer || i == a) {
            continue;
        }
        dfs(i, -1, a);
    }
    return f;
}
int le = -1, pre[1000005];
void dfscyc(int i, int p) {
    if (le != -1) {
        return;
    }
    if (vis[i] == timer) {
        set<int> b;
        pre[i] = p;
        int a = i;
        le = 0;
        a = pre[a];
        if (st.count(a)) {
            if (calc(a)) {
                b.insert(a);
            }
        }
        while(a != i) {
            a = pre[a];
            if (st.count(a)) {
                if (calc(a)) {
                    b.insert(a);
                }
            }
        }
        st = b;
        return;
    }
    vis[i] = timer;
    pre[i] = p;
    for (int j : adj[i]) {
        if (j == p) {
            continue;
        }
        dfscyc(j, i);
    }
}
void cycle(int a) {
    timer++;
    le = -1;
    dfscyc(a, 0);
}
bool cyc = 1, cant = 0;
int s4 = -1;
void Link(int A, int B) {
    adj[A].push_back(B);
    adj[B].push_back(A);
    if (cant || st.size() == 0) {
        return;
    }
    if (find(A) == find(B)) {
        cycle(A);
    }
    if (find(A) != find(B)) {
        merge(A, B);
    }
    if (adj[A].size() >= 4 && s4 == -1) {
        cyc = 0;
        s4 = A;
        if (st.count(A) && calc(A)) {
            st = {A};
        } else {
            st = {};
        }
    }
    if (adj[B].size() >= 4 && s4 == -1) {
        cyc = 0;
        s4 = B;
        if (st.count(B) && calc(B)) {
            st = {B};
        } else {
            st = {};
        }
    }
    if (adj[A].size() >= 4 && s4 != -1 && s4 != A) {
        st.clear();
        cant = 1;
        return;
    }
    if (adj[B].size() >= 4 && s4 != -1 && s4 != B) {
        st.clear();
        cant = 1;
        return;
    }
    if (adj[A].size() == 3) {
        set<int> b;
        if (st.count(A)) {
            if (calc(A)) {
                b.insert(A);
            }
        }
        for (int j : adj[A]) {
            if (st.count(j)) {
                if (calc(j)) {
                    b.insert(j);
                }
            }
        }
        st = b;
    }
    if (adj[B].size() == 3) {
        set<int> b;
        if (st.count(B)) {
            if (calc(B)) {
                b.insert(B);
            }
        }
        for (int j : adj[B]) {
            if (st.count(j)) {
                if (calc(j)) {
                    b.insert(j);
                }
            }
        }
        st = b;
    }
}
int CountCritical() {
    return st.size();
}

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