Submission #939802

#	Time	Username	Problem	Language	Result	Execution time	Memory
939802		alextodoran	Tourism (JOI23_tourism)	C++17	0 / 100	2892 ms	39944 KiB

tourism

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

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int BUFFER_SIZE = 65536;

char buffer[BUFFER_SIZE];
int buf_pos = BUFFER_SIZE - 1;

char read_char () {
    if (++buf_pos == BUFFER_SIZE) {
        fread(buffer, BUFFER_SIZE, sizeof(char), stdin);
        buf_pos = 0;
    }
    return buffer[buf_pos];
}
int read_int () {
    char c;
    while (!isdigit(c = read_char()));
    int val = 0;
    do {
        val = val * 10 + (int) (c - '0');
    } while (isdigit(c = read_char()));
    return val;
}

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 + 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 p2[N_MAX * 2 + 2];

int range_lca[N_MAX * 2 + 2][LOG_N];
int arg_min_depth (const int &u, const 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 e = p2[r - l + 1];
    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[M_MAX + 2];

int cnt, root;

int occ[N_MAX + 2];
int prv[N_MAX + 2], nxt[N_MAX + 2];
bool seen[N_MAX + 2];

void init (int l, int r) {
    fill(occ + 1, occ + N + 1, 0);
    root = 0;
    for (int i = l; i <= r; i++) {
        if (++occ[C[i]] == 1) {
            root = (root == 0 ? C[i] : lca(root, C[i]));
        }
    }
    fill(prv, prv + N + 2, 0);
    fill(nxt, nxt + N + 2, 0);
    fill(seen + 1, seen + N + 1, false);
    cnt = 1;
    int last = 0;
    for (int i = 1; i <= N; i++) {
        int u = order[i];
        if (occ[u] > 0) {
            prv[i] = last;
            nxt[last] = i;
            last = i;
            while (seen[u] == false && u != root) {
                cnt++;
                seen[u] = true;
                u = parent[u];
            }
        }
    }
    nxt[last] = N + 1;
    prv[N + 1] = last;
}
void del (int u) {
    if (--occ[u] == 0) {
        nxt[prv[L[u]]] = nxt[L[u]];
        prv[nxt[L[u]]] = prv[L[u]];
        int ul = order[prv[L[u]]], ur = order[nxt[L[u]]];
        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];
        }
        int v = lca(order[nxt[0]], order[prv[N + 1]]);
        cnt -= depth[v] - depth[root];
        root = v;
    }
}
void add (int u) {
    if (++occ[u] == 1) {
        nxt[prv[L[u]]] = L[u];
        prv[nxt[L[u]]] = L[u];
    }
}

int answer[Q_MAX + 2];

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

    N = read_int();
    M = read_int();
    Q = read_int();
//    N = M = Q = 100000;
    for (int i = 1; i <= N - 1; i++) {
        int u, v;
        u = read_int();
        v = read_int();
//        u = rnd() % i + 1;
//        v = i + 1;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= M; i++) {
        C[i] = read_int();
//        C[i] = i;
    }
//    shuffle(C + 1, C + M + 1, rnd);
    for (int i = 1; i <= Q; i++) {
        ql[i] = read_int();
        qr[i] = read_int();
//        ql[i] = rnd() % M + 1;
//        qr[i] = rnd() % M + 1;
        if (ql[i] > qr[i]) {
            swap(ql[i], qr[i]);
        }
    }
    for (int i = 1; i <= N * 2; i++) {
        p2[i] = p2[i - 1];
        if ((1 << (p2[i] + 1)) <= i) {
            p2[i]++;
        }
    }
    depth[1] = 1;
    dfs(1);
    precalc();
    bucket = max(1, min(M, (int) sqrt(M)));
    for (int i = 1; i <= Q; i++) {
        queries[get_bucket(ql[i])].push_back(i);
    }
    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 bl = (b - 1) * bucket + 1, br = min(M, b * bucket);
        init(bl, br);
        for (int i : queries[b]) {
            if (get_bucket(qr[i]) == b) {
                int prv_cnt = cnt, prv_root = root;
                for (int j = bl; j <= br; j++) {
                    if (j < ql[i] || qr[i] < j) {
                        del(C[j]);
                    }
                }
                answer[i] = cnt;
                for (int j = br; j >= bl; j--) {
                    if (j < ql[i] || qr[i] < j) {
                        add(C[j]);
                    }
                }
                cnt = prv_cnt; root = prv_root;
            }
        }
        init(bl, M);
        int r = M;
        for (int i : queries[b]) {
            if (get_bucket(qr[i]) > b) {
                while (qr[i] < r) {
                    del(C[r--]);
                }
                int prv_cnt = cnt, prv_root = root;
                for (int j = bl; j <= ql[i] - 1; j++) {
                    del(C[j]);
                }
                answer[i] = cnt;
                for (int j = ql[i] - 1; j >= bl; j--) {
                    add(C[j]);
                }
                cnt = prv_cnt; root = prv_root;
            }
        }
    }
    for (int i = 1; i <= Q; i++) {
        cout << answer[i] << "\n";
    }

    return 0;
}

Compilation message (stderr)

tourism.cpp: In function 'char read_char()':
tourism.cpp:22:14: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         fread(buffer, BUFFER_SIZE, sizeof(char), stdin);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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