Submission #296986

#	Time	Username	Problem	Language	Result	Execution time	Memory
296986		Aldas25	늑대인간 (IOI18_werewolf)	C++14	15 / 100	4096 ms	31632 KiB

werewolf

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

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1,(n))
#define f first
#define s second
#define pb push_back
typedef vector<int> vi;
typedef pair<int, int> pii;

const int MAXN = 200100;

bool vis[MAXN];
bool ok = false;
vi adj[MAXN];
int cnt[MAXN];

void dfs (int v, int l, int r) {
    vis[v] = true;
    cnt[v]++;
    for (int u : adj[v]) {
        if (l <= u && u <= r && !vis[u])
            dfs(u, 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 Q = S.size();
    int m = (int)X.size();
    std::vector<int> A(Q);
    FOR(i, 0, m-1) {
        int u = X[i], v = Y[i];
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for (int i = 0; i < Q; ++i) {
        ok = false;
        FOR(j, 0, n-1) cnt[j] = 0;
        FOR(j, 0, n-1) vis[j] = 0;
        dfs (S[i], L[i], n-1);
        FOR(j, 0, n-1) vis[j] = 0;
        dfs (E[i], 0, R[i]);
        FOR(j, 0, n-1) if (cnt[j] > 1) ok  = true;
        A[i] = ok;
        //cout << "  ans: " << A[i] << endl;
    }
    return A;
}

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