Submission #1225628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225628		nicolo_010	Werewolf (IOI18_werewolf)	C++20	15 / 100	4094 ms	43936 KiB

werewolf

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
using ll  = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)
template<typename T>
using v = vector<T>;
const int MOD = 1e9+7;

v<v<int>> adj;
v<v<bool>> vis;
int l, r;
bool can;
int e;

bool check(int x, int t) {
    if (t == 0) {
        return (x >= l);
    }
    else {
        return x <= r;
    }
}

void dfs(int n, int t) {
    vis[n][t] = true;
    if (n == e) can = true;
    for (auto x : adj[n]) {

        if (vis[x][t] == false && check(x, t)) {
            dfs(x, t);
        }
        if (t == 0 && l <= n && n <= r) {
            if (vis[x][1] == false && check(x, 1)) dfs(x, 1);
        }
    }
}

v<int> check_validity(int N, v<int> X, v<int> Y, v<int> S, v<int> E, v<int> L, v<int> R) {
    int n = N;
    adj.resize(n);
    int m = X.size();
    rep(i, 0, m){
        int a = X[i], b = Y[i];
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int q = L.size();
    v<int> ans(q);
    rep(i, 0, q) {
        vis.assign(n, v<bool>(2, false));
        l = L[i], r = R[i];
        e = E[i];
        can = false;
        dfs(S[i], 0);
        if (can) ans[i] = 1;
        else ans[i] = 0;
    }
    return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51