제출 #609552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
609552		skittles1412	늑대인간 (IOI18_werewolf)	C++17	15 / 100	4072 ms	89076 KiB

werewolf

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using vi = vector<int>;

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

template <typename T>
ostream& operator<<(ostream& out, const vector<T> &arr) {
    for (int i = 0; i < sz(arr); i++) {
        if (i) {
            out << " ";
        }
        out << arr[i];
    }
    return out;
}

struct DSU {
    vector<int> p;

    DSU(int n) : p(n, -1) {}

    int find(int u) {
        return p[u] < 0 ? u : find(p[u]);
    }

    void merge(int u, int v) {
        u = find(u);
        v = find(v);
        if (u != v) {
            p[u] = v;
        }
    }
};

struct Tree {
    int n;
    vector<int> ord;
    vector<pair<int, int>> ranges;
    vector<vector<int>> lift, graph;

    Tree(const vector<int>& p)
        : n(sz(p)), ranges(n), lift(__lg(n) + 2, vector<int>(n)), graph(n) {
        vector<int> roots;
        for (int i = 0; i < n; i++) {
            if (p[i] >= 0) {
                graph[p[i]].push_back(i);
            } else {
                roots.push_back(i);
            }
        }
        for (auto& a : roots) {
            dfs(a);
        }
        lift[0] = p;
        for (int i = 0; i <= __lg(n); i++) {
            for (int j = 0; j < n; j++) {
                if (lift[i][j] == -1) {
                    lift[i + 1][j] = -1;
                } else {
                    lift[i + 1][j] = lift[i][lift[i][j]];
                }
            }
        }
    }

    void dfs(int u) {
        ranges[u].first = sz(ord);
        ord.push_back(u);
        for (auto& v : graph[u]) {
            dfs(v);
        }
        ranges[u].second = sz(ord);
    }

    template <typename T>
    pair<int, int> bsearch(int u, const T& t) {
        for (int i = __lg(n); i >= 0; i--) {
            int v = lift[i][u];
            if (v != -1 && t(v)) {
                u = v;
            }
        }
        return ranges[u];
    }
};

vector<int> solve(const vector<int>& arr1,
                  const vector<int>& arr2,
                  const vector<array<int, 4>>& queries) {
    int n = sz(arr1), q = sz(queries);
    assert(sz(arr1) == sz(arr2));
    vector<int> ans(q);
    for (int qi = 0; qi < q; qi++) {
        auto& [l1, r1, l2, r2] = queries[qi];
        bool vis[n] {};
        for (int i = l1; i < r1; i++) {
            vis[arr1[i]] = true;
        }
        for (int i = l2; i < r2; i++) {
            ans[qi] |= vis[arr2[i]];
        }
    }
    return ans;
}

vi check_validity(int n, vi us, vi vs, vi qsrc, vi qdest, vi ql, vi qr) {
    int q = sz(qsrc);
    vector<int> graph[n];
    for (int i = 0; i < sz(us); i++) {
        graph[us[i]].push_back(vs[i]);
        graph[vs[i]].push_back(us[i]);
    }
    DSU inc(n), dec(n);
    for (int i = 0; i < n; i++) {
        for (auto& a : graph[i]) {
            if (a <= i) {
                inc.merge(a, i);
            }
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        for (auto& a : graph[i]) {
            if (a >= i) {
                dec.merge(a, i);
            }
        }
    }
    Tree inct(inc.p), dect(dec.p);
    dbg(inc.p, dec.p);
    vector<array<int, 4>> queries(q);
    dbg(inct.ord, dect.ord);
    for (int qi = 0; qi < q; qi++) {
        int src = qsrc[qi], dest = qdest[qi], l = ql[qi], r = qr[qi];
        auto [il, ir] = inct.bsearch(dest, [&](int x) -> bool {
            return x <= r;
        });
        auto [dl, dr] = dect.bsearch(src, [&](int x) -> bool {
            return x >= l;
        });
        dbg(il, ir, dl, dr);
        queries[qi] = {il, ir, dl, dr};
    }
    return solve(inct.ord, dect.ord, queries);
}

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