Submission #1077007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077007		ArthuroWich	Parachute rings (IOI12_rings)	C++17	38 / 100	4075 ms	85332 KiB

rings

#include<bits/stdc++.h>
using namespace std;
vector<int> adj[1000005], vis;
int n, ans = 0, p[1000005], s[1000005];
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;
}
void Init(int N_) {
    n = N_;
    ans = n;
    for (int i = 0; i < n; i++) {
        p[i] = i;
        s[i] = 1;
    }
}
void dfs(int i, int p, int s) {
    if (vis[i]) {
        f = 0;
        return;
    }
    vis[i] = 1;
    for (int j : adj[i]) {
        if (j == p || j == s) {
            continue;
        }
        dfs(j, i, s);
    }
}
int calc(int a) {
    vis.resize(n, 0);
    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] || i == a) {
            continue;
        }
        dfs(i, -1, a);
    }
    vis.clear();
    return f;
}
int le = -1, pre[1000005];
void dfscyc(int i, int p) {
    if (le != -1) {
        return;
    }
    if (vis[i]) {
        pre[i] = p;
        int a = i;
        le = 0;
        a = pre[a];
        le += calc(a);
        while(a != i) {
            a = pre[a];
            le += calc(a);
        }
        return;
    }
    vis[i] = 1;
    pre[i] = p;
    for (int j : adj[i]) {
        if (j == p) {
            continue;
        }
        dfscyc(j, i);
    }
}
int cycle(int a) {
    vis.resize(n, 0);
    le = -1;
    dfscyc(a, 0);
    vis.clear();
    if (le == -1) {
        le = 0;
    }
    return le;
}
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) {
        return;
    }
    if (cyc && find(A) == find(B)) {
        ans = cycle(A);
    }
    if (find(A) != find(B)) {
        merge(A, B);
    }
    if (adj[A].size() >= 4 && s4 == -1) {
        cyc = 0;
        s4 = A;
        ans = calc(A);
    }
    if (adj[B].size() >= 4 && s4 == -1) {
        cyc = 0;
        s4 = B;
        ans = calc(B);
    }
    if (adj[A].size() >= 4 && s4 != -1 && s4 != A) {
        ans = 0;
        cant = 1;
        return;
    }
    if (adj[B].size() >= 4 && s4 != -1 && s4 != B) {
        ans = 0;
        cant = 1;
        return;
    }
    if (adj[A].size() == 3) {
        ans = calc(A);
        for (int j : adj[A]) {
            ans += calc(j);
        }
        if (ans == 0) {
            cant = 1;
            return;
        }
    }
    if (adj[B].size() == 3) {
        ans = calc(B);
        for (int j : adj[B]) {
            ans += calc(j);
        }
        if (ans == 0) {
            cant = 1;
            return;
        }
    }
}
int CountCritical() {
    return ans;
}

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