oj.uz

Submission #939827

# Submission time Handle Problem Language Result Execution time Memory
939827 2024-03-06T19:34:10 Z alextodoran Tourism (JOI23_tourism) C++17
100 / 100
 3576 ms 39856 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); 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 (r > qr[i]) {
                    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
5.0 / 5.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 2 ms 9820 KB Output is correct
4 Correct 2 ms 9796 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9816 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 2 ms 9816 KB Output is correct
10 Correct 2 ms 9816 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 2 ms 9820 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 2 ms 9820 KB Output is correct
18 Correct 2 ms 9808 KB Output is correct
19 Correct 2 ms 9820 KB Output is correct
20 Correct 2 ms 9820 KB Output is correct
21 Correct 2 ms 9820 KB Output is correct
22 Correct 2 ms 9820 KB Output is correct
23 Correct 2 ms 9816 KB Output is correct
24 Correct 2 ms 9820 KB Output is correct
25 Correct 3 ms 9820 KB Output is correct
26 Correct 2 ms 9820 KB Output is correct
27 Correct 3 ms 9820 KB Output is correct
28 Correct 2 ms 9808 KB Output is correct
29 Correct 2 ms 9816 KB Output is correct

Subtask #2
5.0 / 5.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 2 ms 9820 KB Output is correct
4 Correct 2 ms 9796 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9816 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 2 ms 9816 KB Output is correct
10 Correct 2 ms 9816 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 2 ms 9820 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 2 ms 9820 KB Output is correct
18 Correct 2 ms 9808 KB Output is correct
19 Correct 2 ms 9820 KB Output is correct
20 Correct 2 ms 9820 KB Output is correct
21 Correct 2 ms 9820 KB Output is correct
22 Correct 2 ms 9820 KB Output is correct
23 Correct 2 ms 9816 KB Output is correct
24 Correct 2 ms 9820 KB Output is correct
25 Correct 3 ms 9820 KB Output is correct
26 Correct 2 ms 9820 KB Output is correct
27 Correct 3 ms 9820 KB Output is correct
28 Correct 2 ms 9808 KB Output is correct
29 Correct 2 ms 9816 KB Output is correct
30 Correct 4 ms 10076 KB Output is correct
31 Correct 5 ms 10092 KB Output is correct
32 Correct 7 ms 10332 KB Output is correct
33 Correct 6 ms 10332 KB Output is correct
34 Correct 7 ms 10332 KB Output is correct
35 Correct 4 ms 10332 KB Output is correct
36 Correct 5 ms 10304 KB Output is correct
37 Correct 4 ms 10328 KB Output is correct
38 Correct 6 ms 10332 KB Output is correct
39 Correct 6 ms 10332 KB Output is correct
40 Correct 5 ms 10328 KB Output is correct
41 Correct 5 ms 10332 KB Output is correct
42 Correct 5 ms 10332 KB Output is correct
43 Correct 5 ms 10332 KB Output is correct
44 Correct 6 ms 10332 KB Output is correct
45 Correct 7 ms 10360 KB Output is correct
46 Correct 5 ms 10340 KB Output is correct
47 Correct 4 ms 10332 KB Output is correct
48 Correct 5 ms 10332 KB Output is correct
49 Correct 4 ms 10332 KB Output is correct
50 Correct 6 ms 10332 KB Output is correct
51 Correct 6 ms 10332 KB Output is correct
52 Correct 6 ms 10332 KB Output is correct
53 Correct 6 ms 10332 KB Output is correct
54 Correct 6 ms 10332 KB Output is correct
55 Correct 7 ms 10332 KB Output is correct
56 Correct 3 ms 9820 KB Output is correct
57 Correct 3 ms 10076 KB Output is correct
58 Correct 6 ms 10332 KB Output is correct

Subtask #3
7.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 9820 KB Output is correct
4 Correct 930 ms 28332 KB Output is correct
5 Correct 720 ms 33364 KB Output is correct
6 Correct 1059 ms 36692 KB Output is correct
7 Correct 1520 ms 38824 KB Output is correct
8 Correct 1471 ms 38832 KB Output is correct
9 Correct 1448 ms 38996 KB Output is correct
10 Correct 1527 ms 38860 KB Output is correct
11 Correct 1572 ms 38848 KB Output is correct
12 Correct 451 ms 38364 KB Output is correct
13 Correct 458 ms 38404 KB Output is correct
14 Correct 447 ms 38360 KB Output is correct
15 Correct 37 ms 37420 KB Output is correct
16 Correct 1518 ms 39436 KB Output is correct
17 Correct 166 ms 12280 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 793 ms 23696 KB Output is correct
3 Correct 1527 ms 23700 KB Output is correct
4 Correct 1254 ms 24764 KB Output is correct
5 Correct 938 ms 31232 KB Output is correct
6 Correct 878 ms 31228 KB Output is correct
7 Correct 915 ms 31224 KB Output is correct
8 Correct 1022 ms 31228 KB Output is correct
9 Correct 1383 ms 31224 KB Output is correct
10 Correct 2347 ms 31236 KB Output is correct
11 Correct 2185 ms 31256 KB Output is correct
12 Correct 2293 ms 31568 KB Output is correct
13 Correct 2184 ms 31680 KB Output is correct
14 Correct 2064 ms 31912 KB Output is correct
15 Correct 2314 ms 33540 KB Output is correct
16 Correct 1306 ms 31388 KB Output is correct
17 Correct 1515 ms 31616 KB Output is correct
18 Correct 1422 ms 31652 KB Output is correct
19 Correct 917 ms 31340 KB Output is correct
20 Correct 1012 ms 31224 KB Output is correct
21 Correct 1033 ms 31216 KB Output is correct
22 Correct 1051 ms 31232 KB Output is correct
23 Correct 1121 ms 31248 KB Output is correct
24 Correct 1150 ms 31224 KB Output is correct
25 Correct 1128 ms 31220 KB Output is correct
26 Correct 1506 ms 31264 KB Output is correct
27 Correct 1782 ms 31252 KB Output is correct
28 Correct 1441 ms 31312 KB Output is correct
29 Correct 1551 ms 31324 KB Output is correct
30 Correct 1470 ms 31340 KB Output is correct
31 Correct 1657 ms 31424 KB Output is correct
32 Correct 1591 ms 32088 KB Output is correct
33 Correct 2005 ms 32524 KB Output is correct
34 Correct 2230 ms 33252 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 8 ms 9820 KB Output is correct
3 Correct 3 ms 9816 KB Output is correct
4 Correct 1537 ms 26116 KB Output is correct
5 Correct 1621 ms 26172 KB Output is correct
6 Correct 2220 ms 32012 KB Output is correct
7 Correct 2570 ms 33344 KB Output is correct
8 Correct 2759 ms 33368 KB Output is correct
9 Correct 2894 ms 33352 KB Output is correct
10 Correct 3576 ms 33332 KB Output is correct
11 Correct 3499 ms 33356 KB Output is correct
12 Correct 3119 ms 33364 KB Output is correct
13 Correct 3510 ms 33672 KB Output is correct
14 Correct 162 ms 12176 KB Output is correct

Subtask #6
41.0 / 41.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 2 ms 9820 KB Output is correct
4 Correct 2 ms 9796 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9816 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 2 ms 9816 KB Output is correct
10 Correct 2 ms 9816 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 2 ms 9820 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 2 ms 9820 KB Output is correct
18 Correct 2 ms 9808 KB Output is correct
19 Correct 2 ms 9820 KB Output is correct
20 Correct 2 ms 9820 KB Output is correct
21 Correct 2 ms 9820 KB Output is correct
22 Correct 2 ms 9820 KB Output is correct
23 Correct 2 ms 9816 KB Output is correct
24 Correct 2 ms 9820 KB Output is correct
25 Correct 3 ms 9820 KB Output is correct
26 Correct 2 ms 9820 KB Output is correct
27 Correct 3 ms 9820 KB Output is correct
28 Correct 2 ms 9808 KB Output is correct
29 Correct 2 ms 9816 KB Output is correct
30 Correct 4 ms 10076 KB Output is correct
31 Correct 5 ms 10092 KB Output is correct
32 Correct 7 ms 10332 KB Output is correct
33 Correct 6 ms 10332 KB Output is correct
34 Correct 7 ms 10332 KB Output is correct
35 Correct 4 ms 10332 KB Output is correct
36 Correct 5 ms 10304 KB Output is correct
37 Correct 4 ms 10328 KB Output is correct
38 Correct 6 ms 10332 KB Output is correct
39 Correct 6 ms 10332 KB Output is correct
40 Correct 5 ms 10328 KB Output is correct
41 Correct 5 ms 10332 KB Output is correct
42 Correct 5 ms 10332 KB Output is correct
43 Correct 5 ms 10332 KB Output is correct
44 Correct 6 ms 10332 KB Output is correct
45 Correct 7 ms 10360 KB Output is correct
46 Correct 5 ms 10340 KB Output is correct
47 Correct 4 ms 10332 KB Output is correct
48 Correct 5 ms 10332 KB Output is correct
49 Correct 4 ms 10332 KB Output is correct
50 Correct 6 ms 10332 KB Output is correct
51 Correct 6 ms 10332 KB Output is correct
52 Correct 6 ms 10332 KB Output is correct
53 Correct 6 ms 10332 KB Output is correct
54 Correct 6 ms 10332 KB Output is correct
55 Correct 7 ms 10332 KB Output is correct
56 Correct 3 ms 9820 KB Output is correct
57 Correct 3 ms 10076 KB Output is correct
58 Correct 6 ms 10332 KB Output is correct
59 Correct 2 ms 9816 KB Output is correct
60 Correct 2 ms 9820 KB Output is correct
61 Correct 3 ms 9820 KB Output is correct
62 Correct 930 ms 28332 KB Output is correct
63 Correct 720 ms 33364 KB Output is correct
64 Correct 1059 ms 36692 KB Output is correct
65 Correct 1520 ms 38824 KB Output is correct
66 Correct 1471 ms 38832 KB Output is correct
67 Correct 1448 ms 38996 KB Output is correct
68 Correct 1527 ms 38860 KB Output is correct
69 Correct 1572 ms 38848 KB Output is correct
70 Correct 451 ms 38364 KB Output is correct
71 Correct 458 ms 38404 KB Output is correct
72 Correct 447 ms 38360 KB Output is correct
73 Correct 37 ms 37420 KB Output is correct
74 Correct 1518 ms 39436 KB Output is correct
75 Correct 166 ms 12280 KB Output is correct
76 Correct 2 ms 9820 KB Output is correct
77 Correct 793 ms 23696 KB Output is correct
78 Correct 1527 ms 23700 KB Output is correct
79 Correct 1254 ms 24764 KB Output is correct
80 Correct 938 ms 31232 KB Output is correct
81 Correct 878 ms 31228 KB Output is correct
82 Correct 915 ms 31224 KB Output is correct
83 Correct 1022 ms 31228 KB Output is correct
84 Correct 1383 ms 31224 KB Output is correct
85 Correct 2347 ms 31236 KB Output is correct
86 Correct 2185 ms 31256 KB Output is correct
87 Correct 2293 ms 31568 KB Output is correct
88 Correct 2184 ms 31680 KB Output is correct
89 Correct 2064 ms 31912 KB Output is correct
90 Correct 2314 ms 33540 KB Output is correct
91 Correct 1306 ms 31388 KB Output is correct
92 Correct 1515 ms 31616 KB Output is correct
93 Correct 1422 ms 31652 KB Output is correct
94 Correct 917 ms 31340 KB Output is correct
95 Correct 1012 ms 31224 KB Output is correct
96 Correct 1033 ms 31216 KB Output is correct
97 Correct 1051 ms 31232 KB Output is correct
98 Correct 1121 ms 31248 KB Output is correct
99 Correct 1150 ms 31224 KB Output is correct
100 Correct 1128 ms 31220 KB Output is correct
101 Correct 1506 ms 31264 KB Output is correct
102 Correct 1782 ms 31252 KB Output is correct
103 Correct 1441 ms 31312 KB Output is correct
104 Correct 1551 ms 31324 KB Output is correct
105 Correct 1470 ms 31340 KB Output is correct
106 Correct 1657 ms 31424 KB Output is correct
107 Correct 1591 ms 32088 KB Output is correct
108 Correct 2005 ms 32524 KB Output is correct
109 Correct 2230 ms 33252 KB Output is correct
110 Correct 2 ms 9816 KB Output is correct
111 Correct 8 ms 9820 KB Output is correct
112 Correct 3 ms 9816 KB Output is correct
113 Correct 1537 ms 26116 KB Output is correct
114 Correct 1621 ms 26172 KB Output is correct
115 Correct 2220 ms 32012 KB Output is correct
116 Correct 2570 ms 33344 KB Output is correct
117 Correct 2759 ms 33368 KB Output is correct
118 Correct 2894 ms 33352 KB Output is correct
119 Correct 3576 ms 33332 KB Output is correct
120 Correct 3499 ms 33356 KB Output is correct
121 Correct 3119 ms 33364 KB Output is correct
122 Correct 3510 ms 33672 KB Output is correct
123 Correct 162 ms 12176 KB Output is correct
124 Correct 3249 ms 33624 KB Output is correct
125 Correct 1749 ms 32076 KB Output is correct
126 Correct 3361 ms 33780 KB Output is correct
127 Correct 2628 ms 33780 KB Output is correct
128 Correct 2916 ms 33756 KB Output is correct
129 Correct 3137 ms 33780 KB Output is correct
130 Correct 2692 ms 33772 KB Output is correct
131 Correct 1801 ms 38996 KB Output is correct
132 Correct 1936 ms 39856 KB Output is correct
133 Correct 1975 ms 36800 KB Output is correct
134 Correct 1820 ms 33824 KB Output is correct
135 Correct 1756 ms 33784 KB Output is correct
136 Correct 1784 ms 33784 KB Output is correct
137 Correct 3223 ms 34092 KB Output is correct
138 Correct 3125 ms 34104 KB Output is correct
139 Correct 3086 ms 34084 KB Output is correct
140 Correct 2888 ms 34084 KB Output is correct
141 Correct 3028 ms 34092 KB Output is correct
142 Correct 2934 ms 34088 KB Output is correct
143 Correct 38 ms 31692 KB Output is correct
144 Correct 2441 ms 33284 KB Output is correct