Submission #1031440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031440		mdn2002	Tourism (JOI23_tourism)	C++17	34 / 100	5086 ms	28256 KiB

tourism

/*
Mayoeba Yabureru
*/
#include<bits/stdc++.h>
using namespace std;
struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n;

    FenwickTree(int n) {
        this->n = n;
        bit.assign(n, 0);
    }

    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    FenwickTree bit(m + 1);
    vector<vector<int>> gr(n + 1);
    vector st(n + 1, vector<int> (20));
    vector<int> dp(n + 1);
    for (int i = 1; i < n; i ++) {
        int x, y;
        cin >> x >> y;
        gr[x].push_back(y);
        gr[y].push_back(x);
    }
    function<void(int, int)> dfs = [&] (int x, int p) {
        st[x][0] = p;
        dp[x] = dp[p] + 1;
        for (auto u : gr[x]) {
            if (u == p) continue;
            dfs(u, x);
        }
    };
    dfs(1, 0);
    for (int j = 1; j <= 19; j ++) {
        for (int i = 1; i <= n; i ++) st[i][j] = st[st[i][j - 1]][j - 1];
    }
    function lca = [&] (int x, int y) {
        if (dp[x] > dp[y]) swap(x, y);
        int dif = dp[y] - dp[x], bt = 1;
        for (int i = 0; i < 20; i ++) {
            if ((dif & bt)) y = st[y][i];
            bt *= 2;
        }
        if (x == y) return x;
        for (int i = 19; i >= 0; i --) {
            if (st[x][i] != st[y][i]) {
                x = st[x][i];
                y = st[y][i];
            }
        }
        return st[x][0];
    };

    vector<int> c(m + 1), mx(n + 1), ans(q + 1);
    for (int i = 1; i <= m; i ++) cin >> c[i];
    vector qr(m + 1, vector<pair<int, int>>());
    for (int i = 0; i < q; i ++) {
        int l, r;
        cin >> l >> r;
        qr[r].push_back({l, i});
    }
    for (int r = 1; r <= m; r ++) {
        if (r != 1) {
            int z = lca(c[r], c[r - 1]), x = c[r];
            while (true) {
                if (mx[x]) bit.add(mx[x], -1);
                mx[x] = r;
                bit.add(mx[x], 1);
                if (x == z) break;
                x = st[x][0];
            }
            x = c[r - 1];
            while (true) {
                if (x == z) break;
                if (mx[x]) bit.add(mx[x], -1);
                mx[x] = r;
                bit.add(mx[x], 1);
                x = st[x][0];
            }
        }
        for (auto [l, i] : qr[r]) {
            if (l == r) ans[i] = 1;
            else ans[i] = bit.sum(r) - bit.sum(l);
        }
    }

    for (int i = 0; i < q; i ++) cout << ans[i] << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T = 1;
    for (int I = 0; I < T; I ++){
        solve();
    }
}

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