Submission #596085

#	Time	Username	Problem	Language	Result	Execution time	Memory
596085		proma	Parachute rings (IOI12_rings)	C++17	20 / 100	4078 ms	62472 KiB

rings

#include <bits/stdc++.h>

using namespace std;

int n, cnt = 0, used[5005];
vector <int> deg;
vector <vector <int>> g;

void Init(int N_) {
    n = N_;
    deg.resize(n, 0);
    g.resize(n);
}

void Link(int A, int B) {
    deg[A] ++;
    deg[B] ++;
    g[A].push_back(B);
    g[B].push_back(A);
    if (deg[A] == 3) cnt ++;
    if (deg[B] == 3) cnt ++;
}

int cnt1, cnt2, cnt3;

void dfs(int v, int skip) {
    used[v] = 1;
    int degree = 0;
    for (auto i: g[v]) {
        if (!used[i] and i != skip) dfs(i, skip);
        if (i != skip) degree ++;
    }
    if (degree == 1) cnt1 ++;
    if (degree == 2) cnt2 ++;
    if (degree > 2) cnt3 ++;
}

int CountCritical() {
    int res = 0;
    for (int v = 0; v < n; v ++) {
        int flag = 1;
        memset(used, 0, sizeof(used));
        for (int i = 0; i < n; i ++) {
            if (i == v) continue;
            if (!used[i]) {
                cnt1 = cnt2 = cnt3 = 0;
                dfs(i, v);
                if (cnt3) flag = 0;
                if (!cnt1 and cnt2) flag = 0;
            }
        }
        res += flag;
    }
    return res;
}

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