Submission #970866

#	Time	Username	Problem	Language	Result	Execution time	Memory
970866		BestCrazyNoob	Werewolf (IOI18_werewolf)	C++17	100 / 100	619 ms	130260 KiB

werewolf

#include "werewolf.h"
#include <vector>
#include <utility>
#include <array>

using namespace std;
constexpr int INF = 1e9;
constexpr int H = 20;

struct DSU2 {
    // O(log(n))
    vector<int> r;
    DSU2(int n) {
        r.resize(n, -1);
    }
    int repr(int a) {
        return r[a] < 0 ? a : (r[a] = repr(r[a]));
    }
    // a will become the repr
    int join(int a, int b) {
        a = repr(a);
        b = repr(b);
        if (a == b) return -1;
        // use given order
        r[b] = a;
        return b; // after call to repr()
    }
};

struct SegTree {
    vector<int> tree;
    int sz;
    int ql, qr;
    SegTree() {}
    SegTree(int n) {
        sz = 1;
        while (sz < n) sz *= 2;
        tree.resize(2*sz, -1);
    }
    int __query(int ni, int nl, int nr) {
        if (qr <= nl || nr <= ql) return -1;
        if (ql <= nl && nr <= qr) return tree[ni];
        int nm = (nl+nr)/2;
        return max(__query(2*ni, nl, nm), __query(2*ni+1, nm, nr));
    }
    int query(int l, int r) {
        ql = l;
        qr = r;
        return __query(1, 0, sz);
    }
    void set(int i, int x) {
        i += sz;
        tree[i] = x;
        while (i > 1) {
            i /= 2;
            tree[i] = max(tree[2*i], tree[2*i+1]);
        }
    }
};

vector<vector<int>> graph, adj0, adj1;
vector<int> tin0, tin1, tout0, tout1, ans;
int N, M, curr_eul;
SegTree seg;
vector<array<int, H>> anc0, anc1;
// other, q_index
vector<vector<pair<int, int>>> queries;

void setup0() {
    DSU2 maxel(N);
    adj0.resize(N);
    for (int i = 0; i < N; ++i) {
        for (int x: graph[i]) {
            if (x > i) continue;
            const int other = maxel.join(i, x);
            if (other == -1) continue;
            adj0[i].push_back(other);
            adj0[other].push_back(i);
        }
    }
}

void setup1() {
    DSU2 maxel(N);
    adj1.resize(N);
    for (int i = N-1; i >= 0; --i) {
        for (int x: graph[i]) {
            if (x < i) continue;
            const int other = maxel.join(i, x);
            if (other == -1) continue;
            adj1[i].push_back(other);
            adj1[other].push_back(i);
        }
    }
}

void euler(int curr, int prev, vector<vector<int>> &adj, vector<int> &tin, vector<int> &tout, vector<array<int, H>> &anc) {
    tin[curr] = curr_eul++;
    for (int x: adj[curr]) {
        if (x == prev) continue;
        anc[x][0] = curr;
        euler(x, curr, adj, tin, tout, anc);
    }
    tout[curr] = curr_eul;
}

void calc_anc(vector<array<int, H>> &anc) {
    for (int h = 0; h < H-1; ++h) {
        for (auto &arr: anc) {
            arr[h+1] = arr[h] == -1 ? -1 : anc[arr[h]][h];
        }
    }
}

int get_anc0(int x, int d) {
    for (int h = H-1; h >= 0; --h) {
        if (anc0[x][h] != -1 && anc0[x][h] <= d) x = anc0[x][h];
    }
    return x;
}

int get_anc1(int x, int d) {
    for (int h = H-1; h >= 0; --h) {
        if (anc1[x][h] != -1 && anc1[x][h] >= d) x = anc1[x][h];
    }
    return x;
}

void answer(int curr, int prev) {
    for (int x: adj0[curr]) {
        if (x == prev) continue;
        answer(x, curr);
    }
    // mark the current node visited and say when it was visited
    seg.set(tin1[curr], tin0[curr]);
    for (auto [other, q_index]: queries[curr]) {
        ans[q_index] = seg.query(tin1[other], tout1[other]) >= tin0[curr];
    }
}

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 Q = S.size();
    M = X.size();
    ::N = N;

    graph.resize(N);
    for (int m = 0; m < M; ++m) {
        graph[X[m]].push_back(Y[m]);
        graph[Y[m]].push_back(X[m]);
    }
    // trasform into tree
    setup0();
    setup1();

    anc0.resize(N);
    tin0.resize(N);
    tout0.resize(N);
    anc0[N-1][0] = -1;
    curr_eul = 0;
    euler(N-1, -1, adj0, tin0, tout0, anc0);
    calc_anc(anc0);

    anc1.resize(N);
    tin1.resize(N);
    tout1.resize(N);
    anc1[0][0] = -1;
    curr_eul = 0;
    euler(0, -1, adj1, tin1, tout1, anc1);
    calc_anc(anc1);
    
    ans.resize(Q);
    queries.resize(N);
    for (int q = 0; q < Q; ++q) {
        queries[get_anc0(E[q], R[q])].push_back({get_anc1(S[q], L[q]), q});
    }

    seg = SegTree(N);
    answer(N-1, -1);

    return ans;
}

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