oj.uz

Submission #596085

# Submission time Handle Problem Language Result Execution time Memory
596085 2022-07-14T10:38:27 Z proma Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 62472 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 384 ms 596 KB Output is correct
3 Correct 582 ms 672 KB Output is correct
4 Correct 19 ms 388 KB Output is correct
5 Correct 192 ms 572 KB Output is correct
6 Correct 576 ms 796 KB Output is correct
7 Correct 184 ms 472 KB Output is correct
8 Correct 289 ms 600 KB Output is correct
9 Correct 619 ms 692 KB Output is correct
10 Correct 542 ms 660 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 268 ms 62472 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 384 ms 596 KB Output is correct
3 Correct 582 ms 672 KB Output is correct
4 Correct 19 ms 388 KB Output is correct
5 Correct 192 ms 572 KB Output is correct
6 Correct 576 ms 796 KB Output is correct
7 Correct 184 ms 472 KB Output is correct
8 Correct 289 ms 600 KB Output is correct
9 Correct 619 ms 692 KB Output is correct
10 Correct 542 ms 660 KB Output is correct
11 Execution timed out 4078 ms 780 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 384 ms 596 KB Output is correct
3 Correct 582 ms 672 KB Output is correct
4 Correct 19 ms 388 KB Output is correct
5 Correct 192 ms 572 KB Output is correct
6 Correct 576 ms 796 KB Output is correct
7 Correct 184 ms 472 KB Output is correct
8 Correct 289 ms 600 KB Output is correct
9 Correct 619 ms 692 KB Output is correct
10 Correct 542 ms 660 KB Output is correct
11 Execution timed out 4078 ms 780 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 384 ms 596 KB Output is correct
3 Correct 582 ms 672 KB Output is correct
4 Correct 19 ms 388 KB Output is correct
5 Correct 192 ms 572 KB Output is correct
6 Correct 576 ms 796 KB Output is correct
7 Correct 184 ms 472 KB Output is correct
8 Correct 289 ms 600 KB Output is correct
9 Correct 619 ms 692 KB Output is correct
10 Correct 542 ms 660 KB Output is correct
11 Runtime error 268 ms 62472 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -