Submission #939704

#	Time	Username	Problem	Language	Result	Execution time	Memory
939704		alextodoran	Tourism (JOI23_tourism)	C++17	35 / 100	5051 ms	36516 KiB

tourism

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

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int BUFFER_SIZE = 4096;

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 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 mx = N) {
    int i = 0;
    for (int e = p2[mx]; e >= 0 && k > 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 ur = (upos < total ? order[get_kth(upos + 1, N)] : 0);
        if (ur == 0 || R[u] < L[ur]) {
            int ul = (upos > 1 ? order[get_kth(upos - 1, L[u] - 1)] : 0);
            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);
//    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++) {
        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) {
            occ[C[r--]]--;
        }
        cnt = root = 0;
        fill(Fen + 1, Fen + N + 1, 0); total = 0;
    }
    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: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41