Submission #766035

#	Time	Username	Problem	Language	Result	Execution time	Memory
766035		tengiz05	Werewolf (IOI18_werewolf)	C++17	15 / 100	4034 ms	24524 KiB

werewolf

#include "werewolf.h"
#include "iostream"
#include "array"
#include "queue"
#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;

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 m = X.size();
    vector<vector<int>> e(n);
    for (int i = 0; i < m; i++) {
        e[X[i]].push_back(Y[i]);
        e[Y[i]].push_back(X[i]);
    }
    int Q = S.size();
    vector<int> ans(Q);
    for (int i = 0; i < Q; i++) {
        vector<array<int, 2>> dp(n);
        queue<array<int, 2>> q;
        q.push({S[i], 0});
        dp[S[i]][0] = 1;
        while (!q.empty()) {
            auto [u, p] = q.front();
            q.pop();
            if (L[i] <= u && u <= R[i] && p == 0 && !dp[u][1]) {
                dp[u][1] = 1;
                q.push({u, 1});
            }
            for (int v : e[u]) {
                if (!dp[v][p] && ((p == 0 && v >= L[i]) || (p == 1 && v <= R[i]))) {
                    dp[v][p] = 1;
                    q.push({v, p});
                }
            }
        }
        ans[i] = dp[E[i]][1];
    }
    return ans;
}

/*


6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4



*/

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