Submission #1083608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083608		Blistering_Barnacles	Tourism (JOI23_tourism)	C++17	100 / 100	863 ms	29012 KiB

tourism

//Billions of bilious blue blistering barnacles in a thundering typhoon!
//Yesterday is history, tomorrow is a mystery, today is a gift of God, which is why we call it the present.
#include<bits/stdc++.h>
using namespace std;
void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> adj(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v), adj[v].push_back(u);
    }
    vector<int> c(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> c[i];
    }
    vector<vector<pair<int, int>>> qu(m + 1);
    vector<int> ans(q + 1);
    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        if (l == r) ans[i] = 1;
        else qu[r].push_back({l, i});
    }
    vector<int> csz(n + 1), top(n + 1), pr(n + 1), nxt(n + 1), sz(n + 1), dep(n + 1), chain(n + 1), num(n + 1);
    function<void(int, int)> dfs = [&](int v, int par) {
        pr[v] = par;
        nxt[v] = 0;
        sz[v] = 1;
        for (int u: adj[v]) {
            if (u == par) continue;
            dep[u] = dep[v] + 1;
            dfs(u, v);
            if (sz[u] > sz[nxt[v]]) nxt[v] = u;
            sz[v] += sz[u];
        }
    };
    dfs(1, 0);
    int cnt = 1, all = 0;
    function<void(int, int)> hld = [&](int v, int par) {
        chain[v] = cnt;
        num[v] = ++all;
        if (!csz[cnt]) top[cnt] = v;
        csz[cnt]++;
        if (nxt[v]) hld(nxt[v], v);
        for (int u: adj[v]) {
            if (u == par || u == nxt[v]) continue;
            cnt++;
            hld(u, v);
        }
    };
    hld(1, 0);
    set<array<int, 3>> se;
    se.insert({1, n, 1});
    vector<int> bit(m + 1);
    auto update = [&](int i, int val) {
        while (i <= m) {
            bit[i] += val;
            i += i & -i;
        }
    };
    update(1, n);
    auto query = [&](int l, int r) {
        int ret = 0;
        while (r > 0) {
            ret += bit[r];
            r -= r & -r;
        }
        l--;
        while (l > 0) {
            ret -= bit[l];
            l -= l & -l;
        }
        return ret;
    };
    auto change = [&](int l, int r, int val) {
        auto cur = se.lower_bound({l, l, 0});
        if (cur != se.begin()) cur--;
        vector<array<int, 3>> add, rem;
        add.push_back({l, r, val});
        while (cur != se.end() && (*cur)[0] <= r) {
            auto [l1, r1, v1] = *cur;
            if (r1 < l) {
                cur++;
                continue;
            }
            rem.push_back(*cur);
            if (l1 < l) {
                add.push_back({l1, l - 1, v1});
            }
            if (r1 > r) {
                add.push_back({r + 1, r1, v1});
            }
            cur++;
        }
        for (auto b: rem) {
            se.erase(b);
            auto [l1, r1, v1] = b;
            update(v1, -(r1 - l1 + 1));
        }
        for (auto b: add) {
            se.insert(b);
            auto [l1, r1, v1] = b;
            update(v1, (r1 - l1 + 1));
        }
    };
    function<void(int, int, int)> upd = [&](int u, int v, int val) {
        while (chain[u] != chain[v]) {
            if (dep[top[chain[u]]] < dep[top[chain[v]]]) swap(u, v);
            int start = top[chain[u]];
            change(num[start], num[u], val);        
            u = pr[start];
        }
        if (dep[u] > dep[v]) swap(u, v);
        change(num[u], num[v], val);
    };
    for (int i = 1; i <= m; i++) {
        if (i > 1) {
            upd(c[i - 1], c[i], i);
        }
        for (auto [l, j]: qu[i]) {
            ans[j] = query(l + 1, i);
        }
    }
    for (int i = 1; i <= q; i++) {
        cout << ans[i] << "\n";
    }
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
}

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