Submission #588505

#	Time	Username	Problem	Language	Result	Execution time	Memory
588505		georgievskiy	늑대인간 (IOI18_werewolf)	C++17	15 / 100	4035 ms	41884 KiB

werewolf

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

void dfs(int v, vector<vector<int>>& g, vector<int>& used, int l, int r) {
    used[v] = 1;
    for (auto u : g[v]) {
        if (!used[u] && l <= u && u <= r)
            dfs(u, g, used, l, r);
    }
}

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(), q = S.size();
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++)
        g[X[i]].push_back(Y[i]), g[Y[i]].push_back(X[i]);
    vector<int> u1(n), u2(n);
    vector<int> ans(q, 0);
    for (int i = 0; i < q; i++) {
        fill(u1.begin(), u1.end(), 0); fill(u2.begin(), u2.end(), 0);
        dfs(S[i], g, u1, L[i], n);
        dfs(E[i], g, u2, 0, R[i]);
        for (int v = 0; v < n; v++) {
            if (u1[v] && u2[v]) {
                ans[i] = 1;
                break;
            }
        }
    }
    return ans;
}

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