Submission #1197005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197005		madamadam3	Werewolf (IOI18_werewolf)	C++20	100 / 100	1330 ms	203960 KiB

werewolf

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

using namespace std;

#define FOR(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define srt(x) sort(all(x))

typedef long long ll;
using vi = vector<int>;
using vl = vector<ll>;

struct Edge {
    int u, v, w;

    bool operator<(const Edge &other) const {
        return w < other.w;
    }
};

// we need dsu to find the root of node u's current component
struct DSU {
    int n;
    vector<int> par, size;

    DSU(int N) {
        n = N;
        par.assign(n, 0); iota(par.begin(), par.end(), 0);
        size.assign(n, 1); 
    }

    DSU() : n(0) {};

    int find_set(int v) {
        if (par[v] == v) {
            return v;
        }

        return par[v] = find_set(par[v]);
    }

    void unite(int a, int b) {
        a = find_set(a);
        b = find_set(b);

        if (a != b) {
            // if (size[a] < size[b]) swap(a, b); // no union by rank though 
            par[b] = a;
            size[a] += size[b];
        }
    }
};

struct DSUTree {
    int n, m, k; // n = original graph size, m = num edges, k = 2n-1 = kruskal tree size
    DSU dsu;
    vector<vector<int>> adj; // adjlist for dsu tree
    vector<int> value, edgeid; // value of node i (0 for all leaves)
    vector<Edge> edge_list;

    int MAXLOG;
    vector<vector<int>> up;
    int timer;
    vector<int> tin, tout;

    DSUTree(int N, vector<Edge> edges) {
        n = N;
        m = edges.size();
        k = 2 * n - 1;
        edge_list = edges;
        dsu = DSU(k);

        adj.assign(k, vector<int>());
        value.assign(k, 0);
        edgeid.assign(k, 0);

        construct();
    }   

    void dfs(int u, int p) {
        tin[u] = timer++;
        up[u][0] = p;
        for (int i = 1; i < MAXLOG; i++) {
            up[u][i] = up[up[u][i - 1]][i - 1];
        }

        for (auto &v : adj[u]) {
            if (v == p) continue;
            dfs(v, u);
        }

        tout[u] = timer;
    }

    void construct() {
        sort(edge_list.begin(), edge_list.end());
        int cur_anc = n; // who shall we set the ancestor of u and v to for the current merge

        for (int i = 0; i < m; i++) {
            Edge cur = edge_list[i];
            int u = cur.u, v = cur.v, w = cur.w;
            int uhead = dsu.find_set(u), vhead = dsu.find_set(v);

            if (uhead != vhead) {
                dsu.unite(cur_anc, uhead);
                dsu.unite(cur_anc, vhead);

                adj[cur_anc].push_back(uhead);
                adj[cur_anc].push_back(vhead);
                adj[uhead].push_back(cur_anc);
                adj[vhead].push_back(cur_anc);

                value[cur_anc] = w;
                edgeid[cur_anc] = i;
                cur_anc++;
            }
        }

        MAXLOG = 0;
        while (k >= (1 << MAXLOG)) MAXLOG++;

        up.assign(k, vector<int>(MAXLOG, 0));
        tin.assign(k, 0);
        tout.assign(k, 0);
        timer = 0;
        dfs(dsu.find_set(0), dsu.find_set(0));
    }

    bool is_ancestor(int u, int v) {
        return tin[u] <= tin[v] && tout[u] >= tout[v];
    }

    int lca(int u, int v) {
        if (is_ancestor(u, v)) return u;
        if (is_ancestor(v, u)) return v;

        for (int i = MAXLOG - 1; i >= 0; i++) {
            if (!is_ancestor(up[u][i], v)) u = up[u][i];
        }

        return up[u][0];
    }

    int query_pathmax(int u, int v) { // max edge on path from u to v 
        int anc = lca(u, v);
        return value[anc];
    }

    bool can_reach(int u, int v, int x) { // can i reach v from u in first x nodes
        return edgeid[lca(u, v)] < x;
    }
};

struct Node {
    Node *left, *right;
    int sum;

    Node(int val) : left(nullptr), right(nullptr), sum(val) {};

    Node(Node* L, Node* R) {
        left = L;
        right = R;
        sum = 0;

        if (left) sum += left->sum;
        if (right) sum += right->sum; 
    }
};

struct SegTree {
    int n;
    vector<Node*> roots;
    vector<int> arr;

    Node* build(int l, int r) {
        if (l + 1 == r) return new Node(arr[l]);

        int m = l + (r - l) / 2;
        return new Node(build(l, m), build(m, r));
    }

    Node* update(Node *current, int l, int r, int k, int v) {
        if (!(l <= k && k < r)) return current;
        if (l + 1 == r) return new Node(v);

        int m = l + (r - l) / 2;
        return new Node(update(current->left, l, m, k, v), update(current->right, m, r, k, v));
    }

    int query(Node *current, int l, int r, int ql, int qr) {
        if (r <= ql || qr <= l) return 0;
        if (ql <= l && r <= qr) return current->sum;

        int m = l + (r - l) / 2;
        return query(current->left, l, m, ql, qr) + query(current->right, m, r, ql, qr);
    }

    void update(int k, int v) {
        roots.push_back(update(roots.back(), 0, n, k, v));
    }

    int query(int l, int r, int time) {
        return query(roots[time], 0, n, l, r);
    }

    SegTree(int n, vector<int> arr) {
        this->n = n;
        this->arr = arr;

        roots.push_back(build(0, n));
    }
};

/*
  N = num nodes
  X, Y = edges
  S, E = start and end nodes
  L, R = human and werewolf cities
*/

int n, m, q;
vi x, y, s, e, l, r;

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
    int n = N, m = X.size(), q = S.size();
    // 1) Build two KRTs:
    //    DLo for “≤ R” uses w = max(u,v)
    //    DHi for “≥ L” uses w = -min(u,v)
    vector<Edge> edges_lo(m), edges_hi(m);
    FOR(i,0,m) {
        int u = X[i], v = Y[i];
        edges_lo[i] = {u, v, max(u,v)};
        edges_hi[i] = {u, v, -min(u,v)};
    }
    DSUTree DLo(n, edges_lo);
    DSUTree DHi(n, edges_hi);

    int K = 2*n - 1;
    auto &tin_lo  = DLo.tin;
    auto &tout_lo = DLo.tout;
    auto &tin_hi  = DHi.tin;
    auto &tout_hi = DHi.tout;

    // 2) Collect each city as a point (x = tin_hi, y = tin_lo)
    vector<pair<int,int>> pts(n);
    FOR(i,0,n) pts[i] = { tin_hi[i], tin_lo[i] };
    sort(all(pts));

    // 3) Build events: for each query we need to test if
    //    any point lies in [a,b)×[c,d).  We'll do two events
    //    at x=b-1 (+1) and x=a-1 (−1).
    struct Event { int x, y1, y2, idx, sign; };
    vector<Event> events; events.reserve(2*q);

    FOR(i,0,q) {
        int Si = S[i], Ei = E[i], Li = L[i], Ri = R[i];

        // climb DHi so that all merges along S→u have w ≤ -L  ⇔  min(vertex) ≥ L
        int thresh_hi = -Li;
        int u = Si;
        for (int d = DHi.MAXLOG-1; d >= 0; d--) {
            int vup = DHi.up[u][d];
            if (DHi.value[vup] <= thresh_hi) u = vup;
        }
        int a = tin_hi[u], b = tout_hi[u];

        // climb DLo so that all merges along E→v have w ≤ R  ⇔  max(vertex) ≤ R
        int thresh_lo = Ri;
        int v = Ei;
        for (int d = DLo.MAXLOG-1; d >= 0; d--) {
            int vup = DLo.up[v][d];
            if (DLo.value[vup] <= thresh_lo) v = vup;
        }
        int c = tin_lo[v], d2 = tout_lo[v];

        events.push_back({b-1, c, d2, i, +1});
        events.push_back({a-1, c, d2, i, -1});
    }
    sort(all(events), [&](auto &A, auto &B){ return A.x < B.x; });

    // 4) Fenwick tree over y in [0..K)
    vector<int> bit(K+1, 0);
    auto bit_add = [&](int pos, int v) {
        for (int i = pos+1; i <= K; i += i&-i)
            bit[i] += v;
    };
    auto bit_sum = [&](int pos) {
        int s = 0;
        for (int i = pos; i > 0; i -= i&-i)
            s += bit[i];
        return s;
    };
    auto bit_range = [&](int lpos, int rpos) {
        if (lpos >= rpos) return 0;
        return bit_sum(rpos) - bit_sum(lpos);
    };

    // 5) Sweep
    vi acc(q, 0);
    int ptr = 0;
    for (auto &ev : events) {
        // add all points with x ≤ ev.x
        while (ptr < n && pts[ptr].first <= ev.x) {
            bit_add(pts[ptr].second, +1);
            ptr++;
        }
        int cnt = bit_range(ev.y1, ev.y2);
        acc[ev.idx] += ev.sign * cnt;
    }

    // 6) any positive → reachable
    vi ans(q);
    FOR(i,0,q) ans[i] = (acc[i] > 0);
    return ans;
}

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