Submission #335043

#	Time	Username	Problem	Language	Result	Execution time	Memory
335043		12tqian	Werewolf (IOI18_werewolf)	C++17	100 / 100	1558 ms	148316 KiB

werewolf

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

struct DSU {
    std::vector<int> e;
    void init(int n) {
        e = std::vector<int>(n, -1);
    }
    int get(int x) {
        return e[x] < 0 ? x : e[x] = get(e[x]);
    }
    bool same_set(int a, int b) {
        return get(a) == get(b);
    }
    int size(int x) {
        return -e[get(x)];
    }
    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return false;
        if (e[x] > e[y]) std::swap(x, y);
        e[x] += e[y]; e[y] = x;
        return true;
    }
    bool head(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return false;
        e[y] = x;
        return true;
    }
};

struct LCAJump {
    int n;
    std::vector<std::vector<int>> par;
    std::vector<std::vector<int>> adj;
    std::vector<int> depth;
    void init(int _n) {
        n = _n;
        int d = 1;
        while ((1 << d) < n) d++;
        par.assign(d, std::vector<int>(n));
        adj.resize(n);
        depth.resize(n);
    }
    void ae(int x, int y) {
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    void gen(int root = 0) {
        par[0][root] = root;
        dfs(root);
    }
    void dfs(int src = 0) {
        for (int i = 1; i < par.size(); i++) {
            par[i][src] = par[i - 1][par[i - 1][src]];
        }
        for (int nxt: adj[src]) {
            if (nxt == par[0][src]) continue;
            depth[nxt] = depth[par[0][nxt] = src] + 1;
            dfs(nxt);
        }
    }
    int jump(int x, int d) {
        for (int i = 0; i < par.size(); i++) {
            if ((d >> i) & 1) {
                x = par[i][x];
            }
        }
        return x;
    }
    int lca(int x, int y) {
        if (depth[x] < depth[y]) std::swap(x, y);
        x = jump(x, depth[x] - depth[y]);
        if (x == y) return x;
        for (int i = par.size() - 1; i >= 0; i--) {
            int nx = par[i][x];
            int ny = par[i][y];
            if (nx != ny) x = nx, y = ny;
        }
        return par[0][x];
    }
};

template <class T> struct SegTree {
    const T ID = 1e9;
    T comb(T a, T b) {
        return std::min(a, b);
    }
    int n;
    std::vector<T> seg;
    void init(int _n) {
        n = _n;
        seg.assign(2 * n, ID);
    }
    void pull(int p) {
        seg[p] = comb(seg[2 * p], seg[2 * p + 1]);
    }
    void upd(int p, T val) {
        seg[p += n] = val;
        for (p /= 2; p; p /= 2) pull(p);
    }
    void add(int p, T val) {
        seg[p += n] += val;
        for (p /= 2; p; p /= 2) pull(p);
    }
    T query(int l, int r) {
        T ra = ID, rb = ID;
        for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
            if (l & 1) ra = comb(ra, seg[l++]);
            if (r & 1) rb = comb(seg[--r], rb);
        }
        return comb(ra, rb);
    }
};

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) {
    using namespace std;
    int Q = S.size();
    int M = X.size();

    vector<int> ans(Q);
    vector<vector<int>> g1(N), g2(N);
    DSU d1, d2; d1.init(N), d2.init(N);
    vector<vector<int>> adj(N);

    for (int i = 0; i < M; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }

    LCAJump j1, j2;
    j1.init(N), j2.init(N);

    for (int i = 0; i < N; i++) {
        for (int j : adj[i]) {
            if (j > i || d1.same_set(i, j)) continue;
            int u = i;
            int v = d1.get(j);
            g1[u].push_back(v);
            g1[v].push_back(u);
            d1.head(u, v);
            j1.ae(u, v);;
        }
    }

    for (int i = N - 1; i >= 0; i--){ 
        for (int j : adj[i]) {
            if (j < i || d2.same_set(i, j)) continue;
            int u = i;
            int v = d2.get(j);
            g2[u].push_back(v);
            g2[v].push_back(u);
            d2.head(u, v);
            j2.ae(u, v);;
        }
    }

    int r1 = N - 1;
    int r2 = 0;

    vector<array<int, 2>> gap1(N), gap2(N);
    vector<int> o1, o2;

    int ti = 0;
    function<int(int, int)> dfs1 = [&](int src, int par) -> int {
        gap1[src][0] = gap1[src][1] = ti++;
        o1.push_back(src);
        for (int nxt : g1[src]) {
            if (nxt == par) continue;
            gap1[src][1] = max(gap1[src][1], dfs1(nxt, src));
        }
        return gap1[src][1];
    };
    function<int(int, int)> dfs2 = [&](int src, int par) -> int {
        gap2[src][0] = gap2[src][1] = ti++;
        o2.push_back(src);
        for (int nxt : g2[src]) {
            if (nxt == par) continue;
            gap2[src][1] = max(gap2[src][1], dfs2(nxt, src));
        }
        return gap2[src][1];
    };

    dfs1(r1, -1);
    ti = 0;
    dfs2(r2, -1);
    j1.gen(r1);
    j2.gen(r2);

    auto up = [&](int t, LCAJump& L, int src, int high) -> int {
        for (int i = L.par.size() - 1; i >= 0; i--) {
            if (t == 0) { 
                if (L.par[i][src] <= high) src = L.par[i][src];
            } else {
                if (L.par[i][src] >= high) src = L.par[i][src];
            }   
        }

        return src;
    };  

    map<int, int> conv;
    for (int i = 0; i < N; i++) 
        conv[o1[i]] = i;
    vector<int> loc(N);

    for (int i = 0; i < N; i++)
        o1[i] = conv[o1[i]], o2[i] = conv[o2[i]], loc[o2[i]] = i;

    vector<vector<array<int, 4>>> lower(N);

    for (int i = 0; i < Q; i++) {
        int st = S[i];
        int ed = E[i];
        swap(st, ed);

        int c1 = up(0, j1, st, R[i]);
        int c2 = up(1, j2, ed, L[i]);

        lower[gap1[c1][0]].push_back({gap1[c1][1], gap2[c2][0], gap2[c2][1], i});
    }

    SegTree<int> seg;
    seg.init(N);

    for (int i = N - 1; i >= 0; i--) {
        seg.upd(loc[i], i);
        for (auto& qq : lower[i]) {
            if (seg.query(qq[1], qq[2]) <= qq[0]) ans[qq[3]] = 1;
            else ans[qq[3]] = 0;
        }
    }

    return ans;
}

Compilation message (stderr)

werewolf.cpp: In member function 'void LCAJump::dfs(int)':
werewolf.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int i = 1; i < par.size(); i++) {
      |                         ~~^~~~~~~~~~~~
werewolf.cpp: In member function 'int LCAJump::jump(int, int)':
werewolf.cpp:65:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for (int i = 0; i < par.size(); i++) {
      |                         ~~^~~~~~~~~~~~

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