Submission #1248686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248686		countless	Werewolf (IOI18_werewolf)	C++20	34 / 100	1444 ms	589824 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

// as human, we can only reach other nodes such that the next node is either:
// - less than the current node
// - below Ri

// as wolf:
// - greater than the current node
// - above Li

// so every time in a path and we go leq or greq
// we can find bounds L R that allow this edge.
// generalize: there are edges that only certain bounds can take
// how do we query these edges and connectivity quickly?

// instead phrase it from one side
// only consider human
// process in increasing Ri

const int INF = 1e9;

struct segtree {
    int n, t;
    vector<pair<int, int>> tree;
    segtree(vector<int> &a) {
        n = a.size();
        t = 1;
        while (t < n) t <<= 1;
        tree.assign(2*t, {INF, -INF});

        for (int i = 0; i < n; i++) {
            tree[t + i] = {a[i], a[i]};
        }

        for (int i = t-1; i >= 0; i--) {
            tree[i].first = min(tree[i<<1].first, tree[i<<1|1].first);
            tree[i].second = max(tree[i<<1].second, tree[i<<1|1].second);
        }
    }

    void update(int ind, int upd) {
        int i = t + ind;
        tree[i] = {upd, upd};
        for (i >>= 1; i; i >>= 1) {
            tree[i].first = min(tree[i<<1].first, tree[i<<1|1].first);
            tree[i].second = max(tree[i<<1].second, tree[i<<1|1].second);
        }
    }

    pair<int, int> query(int l, int r) {
        l += t, r += t;
        pair<int, int> res = {INF, -INF};
        while (l <= r) {
            if (l & 1) {
                res.first = min(res.first, tree[l].first);
                res.second = max(res.second, tree[l].second);
                l++;
            }

            if (!(r & 1)) {
                res.first = min(res.first, tree[r].first);
                res.second = max(res.second, tree[r].second);
                r--;
            }

            l >>= 1, r >>= 1;
        }

        return res;
    }
};

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 Q = S.size(), M = X.size();
    vector<int> ans(Q);

    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]);
    }

    // find ends then work
    vector<int> id(N, 0), sweep;
    int fir = 0, sec = -1;
    auto dfs = [&](auto &&dfs, int u, int p) -> void {
        sweep.push_back(u);
        sec = u;
        for (auto &v : adj[u]) {
            if (v != p) {
                id[v] = id[u] + 1;
                dfs(dfs, v, u);
            }
        }
    };

    dfs(dfs, fir, -1);
    swap(fir, sec);
    sweep.clear();
    id.assign(N, 0);
    dfs(dfs, fir, -1);

    // build segtree on this
    segtree st(sweep);

    auto left = [&](int idx, int cap, bool up) -> int {
        int l = -1, r = idx;
        while (r - l > 1) {
            int m = (l+r) / 2;
            auto q = st.query(m, idx);
            int v = (up ? q.first : q.second);
            if (up ? (v >= cap) : (v <= cap)) {
                r = m;
            } else {
                l = m;
            }
        }

        return r;
    };

    auto right = [&](int idx, int cap, bool up) -> int {
        int l = idx, r = N;
        while (r - l > 1) {
            int m = (l+r) / 2;
            auto q = st.query(idx, m);
            int v = (up ? q.first : q.second);
            if (up ? (v >= cap) : (v <= cap)) {
                l = m;
            } else {
                r = m;
            }
        }

        return l;
    };

    for (int i = 0; i < Q; i++) {
        if (S[i] < L[i] or E[i] > R[i]) {
            ans[i] = false;
            continue;
        }

        int ps = id[S[i]], pe = id[E[i]];
        int hl = left(ps, L[i], true);
        int hr = right(ps, L[i], true);

        int wl = left(pe, R[i], false);
        int wr = right(pe, R[i], false);

        bool ok = !(hr < wl or wr < hl);
        ans[i] = ok;
    }

    return ans;
}

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