Submission #997792

#	Time	Username	Problem	Language	Result	Execution time	Memory
997792		biank	Werewolf (IOI18_werewolf)	C++17	15 / 100	4059 ms	39804 KiB

werewolf

#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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51