Submission #1236769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236769		minhpk	Tourism (JOI23_tourism)	C++20	0 / 100	5094 ms	51740 KiB

tourism

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

static const int MAXN = 1000005;
static const int MAXE = 3000005;  // Euler tour size up to ~3*N

vector<int> z[MAXN];
int sta[MAXE], fin[MAXE], euler[MAXE];
int high[MAXN];
int tour;
int st[MAXE][23];
int logarit[MAXE];

int block;
int t[MAXN];
struct Query { int l, r, id; };
vector<Query> q;
multiset<int> s;
long long sum_dist;
int res[MAXN];

void dfs(int u, int p) {
    tour++;
    sta[u] = tour;
    euler[tour] = u;
    for (int v : z[u]) {
        if (v == p) continue;
        high[v] = high[u] + 1;
        dfs(v, u);
        tour++;
        euler[tour] = u;
    }
    tour++;
    fin[u] = tour;
    euler[tour] = u;
}

void build_st() {
    for (int i = 1; i <= tour; i++)
        st[i][0] = euler[i];
    for (int j = 1; (1 << j) <= tour; j++) {
        for (int i = 1; i + (1 << j) - 1 <= tour; i++) {
            int a = st[i][j - 1];
            int b = st[i + (1 << (j - 1))][j - 1];
            st[i][j] = (high[a] < high[b] ? a : b);
        }
    }
    // build log table
    logarit[1] = 0;
    for (int i = 2; i <= tour; i++) logarit[i] = logarit[i >> 1] + 1;
}

int lca(int x, int y) {
    int L = min(sta[x], sta[y]);
    int R = max(sta[x], sta[y]);
    int j = logarit[R - L + 1];
    int a = st[L][j];
    int b = st[R - (1 << j) + 1][j];
    return (high[a] < high[b] ? a : b);
}

int dist(int u, int v) {
    int w = lca(u, v);
    return high[u] + high[v] - 2 * high[w];
}

void add(int idx) {
    int x = t[idx];
    if (s.empty()) {
        s.insert(x);
       // sum_dist = 0;
        return;
    }
    auto it = s.lower_bound(x);
    auto it_next = (it == s.end() ? s.begin() : it);
    auto it_prev = (it == s.begin() ? prev(s.end()) : prev(it));
    sum_dist -= dist(*it_prev, *it_next);
    sum_dist += dist(*it_prev, x) + dist(x, *it_next);
    s.insert(it, x);
}

void remove_idx(int idx) {
    int x = t[idx];
    auto it = s.find(x);
    if (it == s.end()) return;
    if (s.size() == 1) {
        s.erase(it);
      //  sum_dist = 0;
        return;
    }
    auto it_prev = (it == s.begin() ? prev(s.end()) : prev(it));
    auto it_next = next(it);
    if (it_next == s.end()) it_next = s.begin();
    sum_dist -= dist(*it_prev, x) + dist(x, *it_next);
    sum_dist += dist(*it_prev, *it_next);
    s.erase(it);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, Q;
    cin >> N >> M >> Q;
    for (int i = 1; i < N; i++) {
        int u, v;
        cin >> u >> v;
        z[u].push_back(v);
        z[v].push_back(u);
    }
    dfs(1, 0);
    build_st();

    for (int i = 1; i <= M; i++) cin >> t[i];
    q.resize(Q);
    for (int i = 0; i < Q; i++) {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    block = max(1, (int)sqrt(M));
    sort(q.begin(), q.end(), [&](const Query &a, const Query &b) {
        int ba = a.l / block, bb = b.l / block;
        if (ba != bb) return ba < bb;
        return a.r < b.r;
    });

    s.clear(); sum_dist = 0;
    int L = q[0].l, R = q[0].r;
    for (int i = L; i <= R; i++) add(i);
    res[q[0].id] = sum_dist / 2 + 1;

    for (int i = 1; i < Q; i++) {
        while (L > q[i].l) add(--L);
        while (R < q[i].r) add(++R);
        while (L < q[i].l) remove_idx(L++);
        while (R > q[i].r) remove_idx(R--);
        res[q[i].id] = sum_dist / 2 + 1;
    }

    for (int i = 0; i < Q; i++) {
        cout << res[i] << '\n';
    }
    return 0;
}

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