Submission #964649

#	Time	Username	Problem	Language	Result	Execution time	Memory
964649		fve5	Werewolf (IOI18_werewolf)	C++17	0 / 100	4066 ms	35152 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;

vector<int> solve_naive(
    int N, int M, int Q,
    vector<int> X, vector<int> Y,
    vector<int> S, vector<int> E,
    vector<int> L, vector<int> R
) {
    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }

    vector<int> ans(Q);
    for (int i = 0; i < Q; i++) {
        vector<array<bool, 2>> visited(N);
        queue<pair<int, bool>> q;

        q.emplace(S[i], 0);
        while (!q.empty()) {
            auto [node, st] = q.front(); q.pop();
            if (visited[node][st]) continue;
            visited[node][st] = true;
            
            for (auto x: adj[node]) {
                if (!st && x >= L[i]) q.emplace(x, st);
                if (st && x <= R[i]) q.emplace(x, st);
            }

            if (L[i] <= node && node <= R[i]) q.emplace(node, !st);
        }

        ans[i] = visited[E[i]][1];
    }

    return ans;
}

vector<int> check_validity(
    int N,
    vector<int> X, vector<int> Y,
    vector<int> S, vector<int> E,
    vector<int> L, vector<int> R
) {
    int M = X.size();
    int Q = S.size();

    if (N <= 3000 && M <= 6000 && Q <= 3000) {
        return solve_naive(N, M, Q, X, Y, S, E, L, R);
    }
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
   54 | }
      | ^

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