제출 #425748

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
425748		KoD	늑대인간 (IOI18_werewolf)	C++17	100 / 100	926 ms	93004 KiB

werewolf

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

template <class T> using Vec = std::vector<T>;

struct UnionFind {
    Vec<int> par;
    Vec<Vec<int>> children;
    UnionFind(const int n) : par(n), children(n) {
        std::iota(par.begin(), par.end(), 0);
    }
    int find(const int u) {
        return par[u] == u ? u : par[u] = find(par[u]);
    }
    void absorb(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) {
            return;
        }
        par[v] = u;
        children[u].push_back(v);
    }
    std::pair<Vec<int>, Vec<std::pair<int, int>>> build(const int root) {
        const int n = (int) par.size();
        Vec<int> ord;
        ord.reserve(n);
        Vec<std::pair<int, int>> range(n);
        int timer = 0;
        auto dfs = [&](auto&& dfs, const int u) -> void {
            range[u].first = timer++;
            ord.push_back(u);
            for (const auto v : children[u]) {
                dfs(dfs, v);
            }
            range[u].second = timer;
        };
        dfs(dfs, root);
        return std::make_pair(std::move(ord), std::move(range));
    }
};

struct Fenwick {
    Vec<int> data;
    Fenwick(const int n): data(n + 1) {}
    void add(int i, const int x) {
        i += 1;
        while (i < (int) data.size()) {
            data[i] += x;
            i += i & -i;
        }
    }
    int get(int i) const {
        int x = 0;
        while (i > 0) {
            x += data[i];
            i -= i & -i;
        }
        return x;
    }
    int fold(const int l, const int r) const {
        return get(r) - get(l);
    }
};

Vec<int> check_validity(int N, Vec<int> X, Vec<int> Y, Vec<int> S, Vec<int> E, Vec<int> L, Vec<int> R) {
    const int M = (int) X.size();
    const int Q = (int) S.size();
    Vec<Vec<int>> graph(N);
    for (int i = 0; i < M; ++i) {
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }
    UnionFind asc(N), dsc(N);
    Vec<Vec<int>> rqs(N), lqs(N);
    for (int i = 0; i < Q; ++i) {
        rqs[R[i]].push_back(i);
        lqs[L[i]].push_back(i);
    }
    Vec<int> rvert(Q), lvert(Q);
    for (int u = 0; u < N; ++u) {
        for (const auto v : graph[u]) {
            if (v < u) {
                asc.absorb(u, v);
            }
        }
        for (const auto q : rqs[u]) {
            rvert[q] = asc.find(E[q]);
        }
    }
    for (int u = N - 1; u >= 0; --u) {
        for (const auto v : graph[u]) {
            if (u < v) {
                dsc.absorb(u, v);
            }
        }
        for (const auto q : lqs[u]) {
            lvert[q] = dsc.find(S[q]);
        }
    }
    const auto [rord, rrange] = asc.build(N - 1);
    const auto [lord, lrange] = dsc.build(0);
    Vec<int> linv(N);
    for (int i = 0; i < N; ++i) {
        linv[lord[i]] = i;
    }
    Vec<Vec<int>> sub(N), add(N);
    for (int i = 0; i < Q; ++i) {
        const auto [l, r] = rrange[rvert[i]];
        sub[l].push_back(i);
        add[r - 1].push_back(i);
    }
    Fenwick fen(N);
    Vec<int> ret(Q);
    for (int i = 0; i < N; ++i) {
        for (const auto q : sub[i]) {
            const auto [u, d] = lrange[lvert[q]];
            ret[q] -= fen.fold(u, d);
        }
        fen.add(linv[rord[i]], 1);
        for (const auto q : add[i]) {
            const auto [u, d] = lrange[lvert[q]];
            ret[q] += fen.fold(u, d);
        }
    }
    for (auto& x : ret) {
        if (x > 0) {
            x = 1;
        }
    }
    return ret;
}

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