Submission #709848

#	Time	Username	Problem	Language	Result	Execution time	Memory
709848		Cyanmond	늑대인간 (IOI18_werewolf)	C++17	15 / 100	4030 ms	34936 KiB

werewolf

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

struct UnionFind {
    int n;
    std::vector<int> data;
    UnionFind(int n_) : n(n_) {
        data.assign(n, -1);
    }

    int find(int v) {
        if (data[v] < 0) return v;
        else return data[v] = find(data[v]);
    }

    void merge(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (data[a] > data[b]) std::swap(a, b);
        data[a] += data[b];
        data[b] = a;
    }
};

constexpr int B = 3;

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) {
    const int M = (int)X.size();
    const int Q = (int)S.size();
    std::vector<int> answer(Q);

    std::vector<std::vector<int>> graph(2 * N);
    for (int i = 0; i < M; ++i) {
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }
    std::vector<char> isSeen(2 * N);
    for (int i = 0; i < Q; ++i) {
        std::fill(isSeen.begin(), isSeen.end(), false);
        std::queue<int> que;
        que.push(S[i]);
        while (not que.empty()) {
            const int f = que.front();
            que.pop();
            if (f < N) {
                if (L[i] <= f and f <= R[i]) {
                    if (not isSeen[f + N]) {
                        isSeen[f + N] = true;
                        que.push(f + N);
                    }
                }
            }
            const int u = f >= N ? f - N : f;
            for (const int t : graph[u]) {
                if (f >= N) {
                    if (t <= R[i]) {
                        if (not isSeen[t + N]) {
                            isSeen[t + N] = true;
                            que.push(t + N);
                        }
                    }
                } else {
                    if (t >= L[i]) {
                        if (not isSeen[t]) {
                            isSeen[t] = true;
                            que.push(t);
                        }
                    }
                }
            }
        }
        answer[i] = isSeen[E[i] + N];
    }
    return answer;
}

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