oj.uz

Submission #997792

# Submission time Handle Problem Language Result Execution time Memory
997792 2024-06-12T22:22:24 Z biank Werewolf (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Execution timed out 4059 ms 39804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory 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 -