제출 #529223

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

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

template <class F> struct RecLambda : private F {
    RecLambda(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

struct UnionFind {
    vector<int> par;
    vector<vector<int>> child;
    UnionFind(const int n) : par(n, -1), child(n) {}
    int find(const int u) {
        return par[u] < 0 ? u : par[u] = find(par[u]);
    }
    int merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return x;
        const int z = (int)par.size();
        par.push_back(-1);
        child.emplace_back();
        par[x] = par[y] = z;
        child[z].push_back(x);
        child[z].push_back(y);
        return z;
    }
    vector<pair<int, int>> order() const {
        vector<pair<int, int>> ret(par.size());
        int timer = 0;
        RecLambda([&](auto&& dfs, const int u) -> void {
            ret[u].first = timer;
            if (child[u].empty()) {
                timer += 1;
            } else {
                for (const int v : child[u]) {
                    dfs(v);
                }
            }
            ret[u].second = timer;
        })((int)par.size() - 1);
        return ret;
    }
};

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

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    const int M = (int)X.size();
    const int Q = (int)S.size();
    vector<vector<int>> graph(N);
    for (int i = 0; i < M; ++i) {
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }
    vector<int> xl(Q), xr(Q);
    vector<int> x(N);
    {
        vector<vector<int>> list(N);
        for (int i = 0; i < Q; ++i) {
            list[L[i]].push_back(i);
        }
        UnionFind human(N);
        vector<int> memo(Q);
        for (int i = N - 1; i >= 0; --i) {
            for (const int j : graph[i]) {
                if (j >= i) {
                    human.merge(i, j);
                }
            }
            for (const int j : list[i]) {
                memo[j] = human.find(S[j]);
            }
        }
        const auto vec = human.order();
        for (int i = 0; i < N; ++i) {
            x[i] = vec[i].first;
        }
        for (int i = 0; i < Q; ++i) {
            xl[i] = vec[memo[i]].first;
            xr[i] = vec[memo[i]].second;
        }
    }
    vector<int> yl(Q), yr(Q);
    vector<int> y(N);
    {
        vector<vector<int>> list(N);
        for (int i = 0; i < Q; ++i) {
            list[R[i]].push_back(i);
        }
        UnionFind wolf(N);
        vector<int> memo(Q);
        for (int i = 0; i < N; ++i) {
            for (const int j : graph[i]) {
                if (j <= i) {
                    wolf.merge(i, j);
                }
            }
            for (const int j : list[i]) {
                memo[j] = wolf.find(E[j]);
            }
        }
        const auto vec = wolf.order();
        for (int i = 0; i < N; ++i) {
            y[i] = vec[i].first;
        }
        for (int i = 0; i < Q; ++i) {
            yl[i] = vec[memo[i]].first;
            yr[i] = vec[memo[i]].second;
        }
    }
    vector<int> add(N);
    for (int i = 0; i < N; ++i) {
        add[x[i]] = y[i];
    }
    vector<int> count(Q);
    vector<vector<int>> start(N), end(N);
    for (int i = 0; i < Q; ++i) {
        start[xl[i]].push_back(i);
        end[xr[i] - 1].push_back(i);
    }
    Fenwick fen(N);
    for (int x = 0; x < N; ++x) {
        for (const int i : start[x]) {
            count[i] -= fen.fold(yl[i], yr[i]);
        }
        fen.add(add[x]);
        for (const int i : end[x]) {
            count[i] += fen.fold(yl[i], yr[i]);
        }
    }
    for (auto& x : count) {
        x = x > 0;
    }
    return count;
}

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