Submission #939606

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
939606	2024-03-06T15:02:53 Z	alextodoran	Tourism (JOI23_tourism)	C++17	0 / 100	3871 ms	24752 KB

tourism

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;
const int M_MAX = 100000;
const int Q_MAX = 100000;
const int LOG_N = 18;

int N, M, Q;
vector <int> adj[N_MAX + 2];
int C[M_MAX + 2];
int ql[Q_MAX + 2], qr[Q_MAX + 2];

int parent[N_MAX + 2];
int depth[N_MAX + 2];
int order[N_MAX + 2];
int L[N_MAX + 2], R[N_MAX + 2];
int curr;
int euler[N_MAX + 2];
int ecurr;

void dfs (int u) {
    euler[++ecurr] = u;
    L[u] = ++curr;
    order[curr] = u;
    for (int v : adj[u]) {
        if (v != parent[u]) {
            parent[v] = u;
            depth[v] = depth[u] + 1;
            dfs(v);
            euler[++ecurr] = u;
        }
    }
    R[u] = curr;
}

int range_lca[N_MAX * 2 + 2][LOG_N];
int arg_min_depth (int u, int v) {
    return (depth[u] < depth[v] ? u : v);
}

int euler_L[N_MAX + 2], euler_R[N_MAX + 2];
void precalc () {
    for (int i = 1; i <= N * 2; i++) {
        range_lca[i][0] = euler[i];
        if (euler_L[euler[i]] == 0) {
            euler_L[euler[i]] = i;
        }
        euler_R[euler[i]] = i;
    }
    for (int e = 1; e < LOG_N; e++) {
        for (int i = 1; i + (1 << e) - 1 <= N * 2; i++) {
            range_lca[i][e] = arg_min_depth(range_lca[i][e - 1],
                range_lca[i + (1 << (e - 1))][e - 1]);
        }
    }
}
int lca (int u, int v) {
    if (u == 0 || v == 0) {
        return 0;
    }
    if (L[u] > L[v]) {
        swap(u, v);
    }
    int l = euler_L[u], r = euler_R[v];
    int len = r - l + 1;
    int e = 31 - __builtin_clz(len);
    return arg_min_depth(range_lca[l][e], range_lca[r - (1 << e) + 1][e]);
}

int bucket;
int get_bucket (int i) {
    return (i - 1) / bucket + 1;
}
vector <int> queries[N_MAX + 2];

int cnt, root;

int Fen[N_MAX + 2];
void update (int pos, int sgn) {
    for (int i = pos; i <= N; i += i & -i) {
        Fen[i] += sgn;
    }
}
int query (int pos) {
    int cnt = 0;
    for (int i = pos; i >= 1; i -= i & -i) {
        cnt += Fen[i];
    }
    return cnt;
}
int get_kth (int k) {
    int i = 0;
    for (int e = LOG_N - 1; e >= 0; e--) {
        if (i + (1 << e) <= N && Fen[i + (1 << e)] < k) {
            i += (1 << e);
            k -= Fen[i];
        }
    }
    return i + 1;
}

int occ[N_MAX + 2];
int total = 0;
void add (int u) {
    if (++occ[u] == 1) {
        update(L[u], +1); total++;
        if (total == 1) {
            cnt = 1; root = u;
            return;
        }
        int upos = query(L[u]);
        int ul = (upos > 1 ? get_kth(upos - 1) : 0);
        int ur = (upos < total ? get_kth(upos + 1) : 0);
        if (ur == 0 || R[u] < L[ur]) {
            ul = lca(u, ul);
            ur = lca(u, ur);
            int v = (depth[ul] > depth[ur] ? ul : ur);
            cnt += depth[u] - depth[v];
            if (depth[v] < depth[root]) {
                cnt += depth[root] - depth[v];
                root = v;
            }
        } else {
            int v = lca(u, root);
            cnt += depth[root] - depth[v];
            root = v;
        }
    }
}
void del (int u) {
    if (--occ[u] == 0) {
        update(L[u], -1); total--;
    }
}

int answer[Q_MAX + 2];

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

    cin >> N >> M >> Q;
    for (int i = 1; i <= N - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= M; i++) {
        cin >> C[i];
    }
    for (int i = 1; i <= Q; i++) {
        cin >> ql[i] >> qr[i];
    }
    depth[1] = 1;
    dfs(1);
    precalc();
    bucket = max(1, min(M, (int) sqrt(M)));
    for (int i = 1; i <= Q; i++) {
        int bl = get_bucket(ql[i]), br = get_bucket(qr[i]);
        if (bl < br) {
            queries[bl].push_back(i);
        } else {
            for (int j = ql[i]; j <= qr[i]; j++) {
                add(C[j]);
            }
            answer[i] = cnt;
            for (int j = qr[i]; j >= ql[i]; j--) {
                del(C[j]);
            }
            cnt = root = 0;
        }
    }
    for (int b = 1; b <= get_bucket(M) - 1; b++) {
        sort(queries[b].begin(), queries[b].end(), [&] (const int &i, const int &j) {
            return qr[i] < qr[j];
        });
        int r = b * bucket;
        for (int i : queries[b]) {
            while (r < qr[i]) {
                add(C[++r]);
            }
            int prv_cnt = cnt, prv_root = root;
            for (int j = b * bucket; j >= ql[i]; j--) {
                add(C[j]);
            }
            answer[i] = cnt;
            for (int j = ql[i]; j <= b * bucket; j++) {
                del(C[j]);
            }
            cnt = prv_cnt; root = prv_root;
        }
        while (r > b * bucket) {
            del(C[r--]);
        }
        cnt = root = 0;
    }
    for (int i = 1; i <= Q; i++) {
        cout << answer[i] << "\n";
    }

    return 0;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	12124 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	12124 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	12124 KB	Output is correct
2	Correct	3 ms	12200 KB	Output is correct
3	Correct	4 ms	12124 KB	Output is correct
4	Incorrect	3871 ms	24752 KB	Output isn't correct
5	Halted	0 ms	0 KB	-