Submission #1236799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236799		minhpk	Tourism (JOI23_tourism)	C++20	100 / 100	4663 ms	82036 KiB

tourism

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

static const int MAXN = 1000005;
static const int MAXE = 3000005;

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

int n, m, q;
int blockSize;
int tArr[MAXN];

struct Query { int l, r, id; };
Query Q[MAXN];

int bit[MAXE];
int freqNode[MAXN];

void fenw_set(int i, int v) {
    for (; i <= tour; i += i & -i) bit[i] += v;
}

int fenw_sum(int i) {
    int s = 0;
    for (; i > 0; i -= i & -i) s += bit[i];
    return s;
}

int fenw_kth(int k) {
    int pos = 0, curr = 0;
    for (int d = 1 << 21; d > 0; d >>= 1) {
        if (pos + d <= tour && curr + bit[pos + d] < k) {
            pos += d;
            curr += bit[pos];
        }
    }
    return pos + 1;
}

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

void buildST() {
    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], b = st[i + (1 << (j-1))][j-1];
            st[i][j] = (highArr[a] < highArr[b] ? a : b);
        }
    }
    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], b = st[R - (1<<j) + 1][j];
    return (highArr[a] < highArr[b] ? a : b);
}

inline int cal(int x, int y) {
    int w = lca(x, y);
    return highArr[x] + highArr[y] - 2 * highArr[w];
}

bool cmpMo(const Query &A, const Query &B) {
    int ba = A.l / blockSize;
    int bb = B.l / blockSize;
    if (ba != bb) return ba < bb;
    if (ba & 1) return A.r < B.r;
    return A.r > B.r;
}

long long sumd = 0;
int ans[MAXN];

void add(int idx) {
    int u = tArr[idx];
    if (freqNode[u]++ == 0) {
        fenw_set(sta[u], +1);
        int cnt = fenw_sum(tour);
        int k = fenw_sum(sta[u]);
        int prev_k = (k == 1 ? cnt : k - 1);
        int next_k = (k == cnt ? 1   : k + 1);
        int u_prev = euler[ fenw_kth(prev_k) ];
        int u_next = euler[ fenw_kth(next_k) ];
        sumd -= cal(u_prev, u_next);
        sumd += cal(u_prev, u) + cal(u, u_next);
    }
}

void remove_idx(int idx) {
    int u = tArr[idx];
    if (--freqNode[u] == 0) {
        int cnt = fenw_sum(tour);
        int k = fenw_sum(sta[u]);
        int prev_k = (k == 1 ? cnt : k - 1);
        int next_k = (k == cnt ? 1   : k + 1);
        int u_prev = euler[ fenw_kth(prev_k) ];
        int u_next = euler[ fenw_kth(next_k) ];
        sumd -= cal(u_prev, u) + cal(u, u_next);
        sumd += cal(u_prev, u_next);
        fenw_set(sta[u], -1);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    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);
    buildST();

    for (int i = 1; i <= m; i++) {
        cin >> tArr[i];
    }
    blockSize = max(1, (int)sqrt(m));
    for (int i = 1; i <= q; i++) {
        cin >> Q[i].l >> Q[i].r;
        Q[i].id = i;
    }
    sort(Q+1, Q+q+1, cmpMo);

    memset(bit, 0, sizeof bit);
    memset(freqNode, 0, sizeof freqNode);
    sumd = 0;

    int L = Q[1].l, R = Q[1].r;
    for (int i = L; i <= R; i++) add(i);
    ans[Q[1].id] = sumd/2 + 1;

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

    for (int i = 1; i <= q; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

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