Submission #868039

#	Time	Username	Problem	Language	Result	Execution time	Memory
868039		vjudge1	Werewolf (IOI18_werewolf)	C++17	15 / 100	4093 ms	23712 KiB

werewolf

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


std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
        int Q = L.size(), M = X.size();
        vector<vector<int>> adj(N);
        for (int i = 0; i < M; i++) adj[X[i]].emplace_back(Y[i]);
        for (int i = 0; i < M; i++) adj[Y[i]].emplace_back(X[i]);

        auto bfs = [&](int u, int l, int r) {
                assert(l <= u && u <= r);
                vector<int> done(N, 0);
                done[u] = 1;
                queue<int> q;
                q.emplace(u);
                while (q.size()) {
                        int u = q.front();
                        q.pop();
                        for (int v : adj[u]) {
                                if (!done[v] && l <= v && v <= r) {
                                        done[v] = 1;
                                        q.emplace(v);
                                }
                        }
                }
                return done;
        };

        vector<int> A(Q);

        for (int i = 0; i < Q; i++) {
                auto ds = bfs(S[i], L[i], N);
                auto de = bfs(E[i], 0, R[i]);
                for (int j = 0; j < N; j++) {
                        if (de[j] && ds[j]) A[i] = 1;
                }
        }

        return A;
}

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