oj.uz

답안 #997792

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
997792 2024-06-12T22:22:24 Z biank 늑대인간 (IOI18_werewolf) C++17
15 / 100
 4000 ms 39804 KB 
#include <bits/stdc++.h>

using namespace std;

#define sz(x) int(x.size())

using vi = vector<int>;

const int MAX_N = 2e5 + 9;

vi adj[MAX_N];

void dfs(int u, vi &vis, int L, int R) {
    vis[u] = 1;
    for (int v : adj[u]) {
        if (!vis[v] && L <= v && v <= R) dfs(v, vis, L, R);
    }
}

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
    int M = sz(X), Q = sz(S);
    for (int i = 0; i < M; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    vi ans(Q, 0);
    for (int i = 0; i < Q; i++) {
        vi human(N, 0), wolf(N, 0);
        dfs(S[i], human, L[i], N - 1);
        dfs(E[i], wolf, 0, R[i]);
        for (int j = 0; j < N; j++) {
            if (human[j] && wolf[j]) {
                ans[i] = 1;
                break;
            }
        }
    }
    return ans;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 1 ms 4952 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 1 ms 4956 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 1 ms 4952 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 1 ms 4956 KB Output is correct
10 Correct 132 ms 5532 KB Output is correct
11 Correct 49 ms 5484 KB Output is correct
12 Correct 15 ms 5468 KB Output is correct
13 Correct 155 ms 5468 KB Output is correct
14 Correct 66 ms 5464 KB Output is correct
15 Correct 157 ms 5464 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4059 ms 39804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 1 ms 4952 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 1 ms 4956 KB Output is correct
10 Correct 132 ms 5532 KB Output is correct
11 Correct 49 ms 5484 KB Output is correct
12 Correct 15 ms 5468 KB Output is correct
13 Correct 155 ms 5468 KB Output is correct
14 Correct 66 ms 5464 KB Output is correct
15 Correct 157 ms 5464 KB Output is correct
16 Execution timed out 4059 ms 39804 KB Time limit exceeded
17 Halted 0 ms 0 KB -