Submission #1171641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171641		Perl32	Tourism (JOI23_tourism)	C++20	100 / 100	594 ms	55572 KiB

tourism

//I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

const int inf = 0x3f3f3f3f;

struct Info {
    int dep = inf, i = -1;

    Info() = default;
    Info(int _dep, int _i) : dep(_dep), i(_i) {}
};

Info operator+(const Info& a, const Info& b) {
    Info res;
    if (a.dep < b.dep) res = a;
    else res = b;
    return res;
}

struct SPT {
    vector<vector<Info>> mat;

    SPT(vector<Info>& a) {
        int n = (int) a.size();
        const int max_log = 32 - __builtin_clz(n);
        mat.resize(max_log);
        mat[0] = a;
        for (int i = 1; i < max_log; ++i) {
            const int l = (1 << i), h = (1 << (i - 1));
            mat[i].resize(n - l + 1);
            for (int j = 0; j < n - l + 1; ++j) {
                mat[i][j] = mat[i - 1][j] + mat[i - 1][j + h];
            }
        }
    }

    Info get(int l, int r) {
        int lvl = 31 - __builtin_clz(r - l + 1);
        return mat[lvl][l] + mat[lvl][r - (1 << lvl) + 1];
    }
};

struct BIT {
    vector<int> t, tm;
    int n, T;

    BIT(int _n) : t(_n + 1), tm(_n + 1, -1), n(_n), T(0) {}

    void extend() { T++; }

    void upd(int i, int v) {
        for (++i; i <= n; i += i & -i) {
            if (tm[i] == T) {
                t[i] += v;
            } else {
                t[i] = v;
                tm[i] = T;
            }
        }
    }

    int get(int r) {
        int res = 0;
        for (; r; r -= r & -r) {
            if (tm[r] == T) res += t[r];
        }
        return res;
    }
};

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> tree(n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    vector<Info> euler;
    vector<int> tin(n), tout(n), dep(n);
    auto Dfs1 = [&](auto&& self, int u, int p) -> void {
        tin[u] = (int) euler.size();
        euler.emplace_back(dep[u], u);
        for (auto to : tree[u]) {
            if (to == p) continue;
            dep[to] = dep[u] + 1;
            self(self, to, u);
            euler.emplace_back(dep[u], u);
        }
        tout[u] = (int) euler.size();
    };
    dep[0] = 0;
    Dfs1(Dfs1, 0, -1);
    SPT spt(euler);
    auto lca = [&](int u, int v) {
        if (tin[u] > tin[v]) swap(u, v);
        return spt.get(tin[u], tin[v]).i;
    };
    auto isp = [&](int u, int v) { return tin[u] <= tin[v] && tout[v] <= tout[u]; };
    vector<int> a(m);
    for (auto& x : a) {
        cin >> x; --x;
    }
    vector<array<int, 2>> qq(q);
    for (auto& [lx, rx] : qq) {
        cin >> lx >> rx;
        --lx, --rx;
    }
    int T = 0;
    vector<vector<pair<int, int>>> g(n);
    auto add_edge = [&](int u, int v, int w) {
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    };
    vector<array<int, 3>> adj;
    vector<int> ans(q, 1), tm(n, -1), lft(n), rig(n);
    auto Dfs2 = [&](auto&& self, int u, int p) -> void {
        if (tm[u] != T) {
            lft[u] = -1; rig[u] = m;
        }
        for (auto [to, w] : g[u]) {
            if (to == p) continue;
            self(self, to, u);
            lft[u] = max(lft[u], lft[to]);
            rig[u] = min(rig[u], rig[to]);
            adj.push_back({lft[to], rig[to], w});
        }
    };
    BIT tt(m + 1);
    auto divi = [&](auto&& self, int lx, int rx, vector<int>& ord) {
        if (lx >= rx) return;
        int mid = (lx + rx) >> 1;
        vector<int> lb, rb, nw;
        for (auto i : ord) {
            auto [ql, qr] = qq[i];
            if (ql <= mid && qr > mid) {
                nw.push_back(i);
            } else if (qr <= mid) {
                lb.push_back(i);
            } else if (ql > mid) {
                rb.push_back(i);
            }
        }
        self(self, lx, mid, lb);
        self(self, mid + 1, rx, rb);
        T++;
        vector<int> aboba;
        for (int i = lx; i <= rx; ++i) {
            int v = a[i];
            if (tm[v] != T) {
                aboba.push_back(v);
                g[v].clear();
                if (i <= mid) {
                    lft[v] = i;
                    rig[v] = m;
                } else {
                    rig[v] = i;
                    lft[v] = -1;
                }
                tm[v] = T;
            }
            if (i <= mid) lft[v] = max(lft[v], i);
            if (i > mid) rig[v] = min(rig[v], i);
        }
        sort(aboba.begin(), aboba.end(), [&](int u, int v) { return tin[u] < tin[v]; });
        int sz = (int) aboba.size();
        for (int i = 0; i + 1 < sz; ++i) aboba.push_back(lca(aboba[i], aboba[i + 1]));
        sort(aboba.begin(), aboba.end(), [&](int u, int v) { return tin[u] < tin[v]; });
        aboba.resize(unique(aboba.begin(), aboba.end()) - aboba.begin());
        sz = (int) aboba.size();
        vector<int> st;
        for (auto u : aboba) {
            if (tm[u] != T) g[u].clear();
            while (!st.empty() && !isp(st.back(), u)) st.pop_back();
            if (!st.empty()) add_edge(st.back(), u, dep[u] - dep[st.back()]);
            st.push_back(u);
        }
        adj.clear();
        Dfs2(Dfs2, a[mid], -1);
        sort(nw.begin(), nw.end(), [&](int i, int j) { return qq[i] > qq[j]; });
        sort(adj.rbegin(), adj.rend());
        int r = 0;
        tt.extend();
        for (auto i : nw) {
            auto [ql, qr] = qq[i];
            while (r < (int) adj.size() && adj[r][0] >= ql) { tt.upd(adj[r][1], adj[r][2]); r++; }
            ans[i] += tt.get(m + 1) - tt.get(qr + 1);
        }
        while (r < (int) adj.size()) { tt.upd(adj[r][1], adj[r][2]); r++; }
        for (auto i : nw) {
            auto [ql, qr] = qq[i];
            ans[i] += tt.get(qr + 1);
        }
    };
    vector<int> ord(q);
    iota(ord.begin(), ord.end(), 0);
    divi(divi, 0, m - 1, ord);
    for (auto x : ans) cout << x << '\n';
}

/*

 */

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41