Submission #434432

#	Time	Username	Problem	Language	Result	Execution time	Memory
434432		dxz05	Werewolf (IOI18_werewolf)	C++14	15 / 100	4059 ms	36716 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 4e5 + 3e2;

vector<int> g[MAXN];

void dfs(int v, int l, int r, vector<bool> &used){
    used[v] = true;

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

}

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 Q = S.size(), M = X.size();
    vector<int> A(Q, 0);

    for (int i = 0; i < M; i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }

    for (int i = 0; i < Q; i++){
        vector<bool> used1(N, false), used2(N, false);
        dfs(S[i], L[i], N - 1, used1);
        dfs(E[i], 0, R[i], used2);

        for (int j = L[i]; j <= R[i]; j++){
            if (used1[j] && used2[j]) A[i] = 1;
        }

    }

    return A;
}

/**
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