oj.uz

답안 #596085

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
596085 2022-07-14T10:38:27 Z proma 낙하산 고리들 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -