Submission #938890

#	Time	Username	Problem	Language	Result	Execution time	Memory
938890		alextodoran	Tourism (JOI23_tourism)	C++17	0 / 100	51 ms	16468 KiB

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 = 17;

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 anc[N_MAX + 2][LOG_N];

int ancestor (int u, int k) {
    for (int e = 0; e < LOG_N; e++) {
        if ((k >> e) & 1) {
            u = anc[u][e];
        }
    }
    return u;
}
int lca (int u, int v) {
    if (u == 0 || v == 0) {
        return 0;
    }
    if (depth[u] > depth[v]) {
        u = ancestor(u, depth[u] - depth[v]);
    }
    if (depth[v] > depth[u]) {
        v = ancestor(v, depth[v] - depth[u]);
    }
    if (u == v) {
        return u;
    }
    for (int e = LOG_N - 1; e >= 0; e--) {
        if (anc[u][e] != anc[v][e]) {
            u = anc[u][e];
            v = anc[v][e];
        }
    }
    return parent[u];
}

void dfs (int 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);
        }
    }
    R[u] = curr;
}

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

int cnt, root;

int occ[N_MAX + 2];
set <int> S;
void add (int u) {
    if (++occ[u] == 1) {
        if (S.empty() == true) {
            S.insert(L[u]);
            cnt = 1; root = u;
            return;
        }
        set <int> :: iterator it = S.insert(L[u]).first;
        int ul = (it != S.begin() ? order[*prev(it)] : 0);
        int ur = (next(it) != S.end() ? order[*next(it)] : 0);
        ul = lca(u, ul);
        ur = lca(u, ur);
        int v = (depth[ul] > depth[ur] ? ul : ur);
        if (ur != u) {
            cnt += depth[u] - depth[v];
        }
        if (L[v] < L[root]) {
            cnt += depth[root] - depth[v];
            root = v;
        }
    }
}
void del (int u) {
    if (--occ[u] == 0) {
        S.erase(L[u]);
    }
}

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);
    for (int u = 1; u <= N; u++) {
        anc[u][0] = parent[u];
    }
    for (int e = 1; e < LOG_N; e++) {
        for (int u = 1; u <= N; u++) {
            anc[u][e] = anc[anc[u][e - 1]][e - 1];
        }
    }
    bucket = max(1, min(N, (int) (N / sqrt(Q))));
    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(N); 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
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41