Submission #1123324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123324		anmattroi	Werewolf (IOI18_werewolf)	C++20	100 / 100	3863 ms	365648 KiB

werewolf

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

using namespace std;


vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {

    int M = X.size();

    vector<int> g1[N+N-1], g2[N+N-1];
    int d1[N+N-1], d2[N+N-1];
    int par[N+N-1], val1[N+N-1], val2[N+N-1];
    int pos1[N+N-1], pos2[N+N-1], id1 = 0, id2 = 0;

    #define fi first
    #define se second
    using ii = pair<int, int>;

    vector<vector<ii> > f(20, vector<ii>(4*N)), g(20, vector<ii>(4*N));

    function<int(int)> find_set = [&](int v) {
        return par[v] == v ? v : par[v] = find_set(par[v]);
    };

    fill(val1, val1 + N + N - 1, N);
    fill(val2, val2 + N + N - 1, 0);

    struct edge {
        int u, v, l;
        edge() {}
        edge(int _u, int _v, int _l) : u(_u), v(_v), l(_l) {}
    } edges[M];

    for (int i = 0; i < M; i++) edges[i] = edge(X[i], Y[i], min(X[i], Y[i]));

    sort(edges, edges + M, [&](edge x, edge y) {
            return x.l > y.l;
         });

    int root1 = N, root2 = N;

    iota(par, par + N + N - 1, 0);

    for (int i = 0; i < M; i++) {
        auto [u, v, l] = edges[i];
        u = find_set(u); v = find_set(v);
        if (u == v) continue;
        g1[root1].emplace_back(u);
        g1[root1].emplace_back(v);
        val1[root1] = l;
        par[u] = root1;
        par[v] = root1;
        ++root1;
    }

    d1[root1-1] = 0;
    function<void(int)> dfs1 = [&](int u) {
        f[0][++id1] = {d1[u], u};
        pos1[u] = id1;
        for (int v : g1[u]) {
            d1[v] = d1[u] + 1;
            dfs1(v);
            f[0][++id1] = {d1[u], u};
        }
    };

    dfs1(root1-1);
    for (int i = 1; (1<<i) <= id1; i++) for (int j = 1; j + (1<<i) - 1 <= id1; j++) f[i][j] = min(f[i-1][j], f[i-1][j+(1<<(i-1))]);

    for (int i = 0; i < M; i++) edges[i] = edge(X[i], Y[i], max(X[i], Y[i]));

    sort(edges, edges + M, [&](edge x, edge y) {
            return x.l < y.l;
         });

    iota(par, par + N + N - 1, 0);

    for (int i = 0; i < M; i++) {
        auto [u, v, l] = edges[i];
        u = find_set(u); v = find_set(v);
        if (u == v) continue;
        g2[root2].emplace_back(u);
        g2[root2].emplace_back(v);
        val2[root2] = l;
        par[u] = root2;
        par[v] = root2;
        ++root2;
    }

    d2[root2-1] = 0;
    function<void(int)> dfs2 = [&](int u) {
        g[0][++id2] = {d2[u], u};
        pos2[u] = id2;
        for (int v : g2[u]) {
            d2[v] = d2[u] + 1;
            dfs2(v);
            g[0][++id2] = {d2[u], u};
        }
    };

    dfs2(root2-1);

    for (int i = 1; (1<<i) <= id2; i++) for (int j = 1; j + (1<<i) - 1 <= id2; j++) g[i][j] = min(g[i-1][j], g[i-1][j+(1<<(i-1))]);


    function<int(int, int)> LCA1 = [&](int u, int v) {
        u = pos1[u]; v = pos1[v];
        if (u > v) swap(u, v);
        int k = __lg(v-u+1);
        return min(f[k][u], f[k][v-(1<<k)+1]).se;
    };

    function<int(int, int)> LCA2 = [&](int u, int v) {
        u = pos2[u]; v = pos2[v];
        if (u > v) swap(u, v);
        int k = __lg(v-u+1);
        return min(g[k][u], g[k][v-(1<<k)+1]).se;
    };

    int st[21*N+5], Lef[21*N+5], Rig[21*N+5];

    int c1[N+1], c2[N+1];

    iota(c1 + 1, c1 + N + 1, 0);
    iota(c2 + 1, c2 + N + 1, 0);

    sort(c1 + 1, c1 + N + 1, [&](int x, int y) {
            return pos1[x] < pos1[y];
         });

    sort(c2 + 1, c2 + N + 1, [&](int x, int y) {
            return pos2[x] < pos2[y];
         });

    int rem[N], root[N+1], nho[N];

    for (int i = 1; i <= N; i++) nho[c1[i]] = i;
    for (int i = 1; i <= N; i++) rem[c2[i]] = i;

    int nt = 0;

    function<int(int, int)> build = [&](int lo, int hi) {
        if (lo == hi) {
            st[++nt] = 0;
            return nt;
        }
        int cur = ++nt, mid = (lo + hi) >> 1;
        Lef[cur] = build(lo, mid);
        Rig[cur] = build(mid+1, hi);
        st[cur] = 0;
        return cur;
    };

    root[0] = build(1, N);

    function<int(int, int, int, int)> upd = [&](int u, int oldver, int lo, int hi) {
        if (lo == hi) {
            st[++nt] = st[oldver] + 1;
            return nt;
        }
        int cur = ++nt, mid = (lo + hi) >> 1;
        if (u <= mid) {
            Lef[cur] = upd(u, Lef[oldver], lo, mid);
            Rig[cur] = Rig[oldver];
        } else {
            Lef[cur] = Lef[oldver];
            Rig[cur] = upd(u, Rig[oldver], mid+1, hi);
        }
        st[cur] = st[Lef[cur]] + st[Rig[cur]];
        return cur;
    };

    function<int(int, int, int, int, int)> get = [&](int u, int v, int r, int lo, int hi) {
        if (u > hi || v < lo) return 0;
        if (u <= lo && hi <= v) return st[r];
        int mid = (lo + hi) >> 1;
        return get(u, v, Lef[r], lo, mid) + get(u, v, Rig[r], mid+1, hi);
    };

    for (int i = 1; i <= N; i++) {
        int u = c1[i];
        root[i] = upd(rem[u], root[i-1], 1, N);
    }

    int Q = S.size();

    vector<int> ans;

    function<void(int)> solve = [&](int idx) {
        int s = S[idx], e = E[idx], l = L[idx], r = R[idx];

        int Leftup, Rightup, Leftdown, Rightdown, lo, hi, cur;

        cur = nho[s];


        lo = cur; hi = N+1;
        while (hi - lo > 1) {
            int mid = (lo + hi) >> 1;
            if (val1[LCA1(s, c1[mid])] >= l) lo = mid;
            else hi = mid;
        }
        Rightup = lo;

        lo = 0; hi = cur;
        while (hi - lo > 1) {
            int mid = (lo + hi) >> 1;
            if (val1[LCA1(s, c1[mid])] >= l) hi = mid;
            else lo = mid;
        }
        Leftup = hi;

        cur = rem[e];

        lo = cur; hi = N+1;
        while (hi - lo > 1) {
            int mid = (lo + hi) >> 1;
            if (val2[LCA2(e, c2[mid])] <= r) lo = mid;
            else hi = mid;
        }
        Rightdown = lo;

        lo = 0; hi = cur;
        while (hi - lo > 1) {
            int mid = (lo + hi) >> 1;
            if (val2[LCA2(e, c2[mid])] <= r) hi = mid;
            else lo = mid;
        }
        Leftdown = hi;

        bool flag = ((get(Leftdown, Rightdown, root[Rightup], 1, N) - get(Leftdown, Rightdown, root[Leftup-1], 1, N)) > 0);
        ans.emplace_back(int(flag));
    };

    for (int o = 0; o < Q; o++) solve(o);

    return ans;
}

/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

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