oj.uz

Submission #939802

# Submission time Handle Problem Language Result Execution time Memory
939802 2024-03-06T19:02:36 Z alextodoran Tourism (JOI23_tourism) C++17
0 / 100
 2892 ms 39944 KB 
/**
 _  _   __  _ _ _  _  _ _
 |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

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.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 3 ms 9812 KB Output is correct
4 Correct 933 ms 29044 KB Output is correct
5 Correct 801 ms 34088 KB Output is correct
6 Correct 1253 ms 37472 KB Output is correct
7 Correct 1524 ms 39832 KB Output is correct
8 Correct 1622 ms 39924 KB Output is correct
9 Correct 1538 ms 39928 KB Output is correct
10 Correct 1650 ms 39944 KB Output is correct
11 Correct 1481 ms 39928 KB Output is correct
12 Correct 461 ms 39368 KB Output is correct
13 Correct 466 ms 39444 KB Output is correct
14 Correct 465 ms 39480 KB Output is correct
15 Incorrect 40 ms 37844 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 791 ms 23632 KB Output is correct
3 Incorrect 1266 ms 24156 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9816 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 1582 ms 26300 KB Output is correct
5 Correct 1598 ms 26336 KB Output is correct
6 Correct 2261 ms 32344 KB Output is correct
7 Correct 2806 ms 33648 KB Output is correct
8 Correct 2785 ms 33560 KB Output is correct
9 Correct 2809 ms 33668 KB Output is correct
10 Correct 2755 ms 33640 KB Output is correct
11 Correct 2777 ms 33872 KB Output is correct
12 Incorrect 2892 ms 33672 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

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