QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#879524#6340. Tourismwoohyun_jng0 665ms25488kbC++233.2kb2025-02-02 05:17:342025-02-02 05:17:36

Judging History

This is the latest submission verdict.

  • [2025-02-02 05:17:36]
  • Judged
  • Verdict: 0
  • Time: 665ms
  • Memory: 25488kb
  • [2025-02-02 05:17:34]
  • Submitted

answer

#include <bits/stdc++.h>
#define int long long

#define MAX 200000

using namespace std;
typedef array<int, 2> pr;
typedef array<int, 3> tp;

vector<pr> queries[MAX];
vector<int> adj[MAX];
set<tp> st;

int N, C[MAX], ans[MAX], in[MAX], top[MAX], parent[MAX], depth[MAX], sz[MAX], tree[MAX * 4], cnt = 0;

void dfs(int node, int par) {
    depth[node] = depth[par] + 1, parent[node] = par, sz[node] = 1;
    for (int &i : adj[node]) {
        if (i == par)
            continue;
        dfs(i, node), sz[node] += sz[i];
        if (adj[node][0] == par || sz[adj[node][0]] < sz[i])
            swap(adj[node][0], i);
    }
}

void hld(int node, int par) {
    in[node] = ++cnt;
    for (int i : adj[node]) {
        if (i == par)
            continue;
        top[i] = i == adj[node][0] ? top[node] : i;
        hld(i, node);
    }
}

int query(int n, int s, int e, int l, int r) {
    if (r < s || e < l)
        return 0;
    else if (l <= s && e <= r)
        return tree[n];
    else {
        int m = s + e >> 1;
        return query(n << 1, s, m, l, r) + query(n << 1 | 1, m + 1, e, l, r);
    }
}

void update(int n, int s, int e, int x, int v) {
    if (x < s || e < x)
        return;
    else if (s == e)
        tree[n] += v;
    else {
        int m = s + e >> 1;
        update(n << 1, s, m, x, v), update(n << 1 | 1, m + 1, e, x, v);
        tree[n] = tree[n << 1] + tree[n << 1 | 1];
    }
}

void upd(int s, int e, int v) {
    set<tp>::iterator iter;
    tp K;

    iter = prev(st.lower_bound({s, N + 1, 0})), K = *iter;
    while (K[1] <= e) {
        st.erase(iter), update(1, 1, N, K[2], -(K[1] - K[0] + 1));
        if (K[0] < s)
            st.insert({K[0], s - 1, K[2]}), update(1, 1, N, K[2], s - K[0]);
        iter = st.lower_bound({s, 0, 0}), K = iter == st.end() ? (tp){0, N + 1, 0} : *iter;
    }
    if (iter != st.end() && K[0] <= e) {
        st.erase(iter), update(1, 1, N, K[2], -(K[1] - K[0] + 1));
        if (K[0] < s)
            st.insert({K[0], s - 1, K[2]}), update(1, 1, N, K[2], s - K[0]);
        st.insert({e + 1, K[1], K[2]}), update(1, 1, N, K[2], K[1] - e);
    }
    st.insert({s, e, v}), update(1, 1, N, v, e - s + 1);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int M, Q, X, Y;
    cin >> N >> M >> Q;

    for (int i = 1; i < N; i++) {
        cin >> X >> Y;
        adj[X].push_back(Y), adj[Y].push_back(X);
    }

    dfs(1, 0), top[1] = 1, hld(1, 0);
    st.insert({1, N, 1}), update(1, 1, N, 1, N);

    for (int i = 1; i <= M; i++)
        cin >> C[i];

    for (int i = 1; i <= Q; i++) {
        cin >> X >> Y;
        queries[Y].push_back({i, X});
    }

    for (int i = 2; i <= M; i++) {
        X = C[i - 1], Y = C[i];
        while (top[X] ^ top[Y]) {
            if (depth[top[X]] < depth[top[Y]])
                swap(X, Y);
            upd(in[top[X]], in[X], i), X = parent[top[X]];
        }
        if (depth[X] > depth[Y])
            swap(X, Y);
        upd(in[X], in[Y], i);

        for (pr j : queries[i])
            ans[j[0]] = query(1, 1, N, j[1] + 1, i);
    }

    for (int i = 1; i <= Q; i++)
        cout << max(1ll, ans[i]) << '\n';

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 14088kb

input:

166 249 224
158 52
52 82
158 36
117 158
119 117
5 82
158 18
22 36
82 143
105 36
22 152
36 92
117 2
123 158
5 134
119 89
31 119
92 48
105 149
149 17
108 31
134 50
3 52
63 158
3 51
42 22
17 10
103 158
50 122
92 85
50 78
117 159
36 20
143 115
158 83
20 4
142 22
23 3
96 10
19 134
8 10
151 92
65 108
89 5...

output:

67
12
74
93
110
43
1
24
82
55
70
25
79
96
25
113
86
60
1
49
34
33
66
33
1
1
43
91
40
28
46
58
73
1
93
1
70
85
25
95
75
69
85
72
33
82
48
32
34
1
99
121
63
56
74
36
1
69
47
48
31
50
1
30
22
120
105
28
36
3
83
63
65
1
34
32
43
1
98
6
122
57
1
105
45
73
105
53
29
95
28
28
52
39
65
91
4
108
23
1
36
53
8...

result:

wrong answer 2nd numbers differ - expected: '97', found: '12'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #56:

score: 0
Wrong Answer
time: 81ms
memory: 25488kb

input:

55321 88650 75523
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:

1
1
55313
55306
55319
53676
1
1
1
1
1
1
55318
1
55311
55311
1
1
1
55319
1
55317
1
55319
1
55318
1
55318
1
1
2
1
55319
1
1
1
1
1
1
1
1
1
1
55186
55204
1
2
55319
55297
1
1
55318
55319
1
55319
1
1
1
1
55319
55318
1
55293
28
1
28
1
55317
1
1
1
1
1
55307
1
1
1
55316
55301
1
55311
55317
55143
1
1
1
55319
...

result:

wrong answer 1st numbers differ - expected: '55319', found: '1'

Subtask #4:

score: 0
Wrong Answer

Test #69:

score: 18
Accepted
time: 282ms
memory: 21588kb

input:

54738 54525 1797
45211 4527
4527 43609
4527 19876
16325 43609
32183 4527
16325 32579
43609 25554
32183 38972
45211 53953
16325 19810
10881 19810
45211 12698
27967 19810
25554 46338
51894 45211
25388 16325
512 25554
43609 7820
10206 512
30021 32183
48647 43609
46338 44138
16766 7820
10023 53953
19810...

output:

276
238
198
214
294
240
233
266
184
241
207
241
256
225
215
222
190
269
221
242
287
225
215
252
273
203
281
186
259
195
152
183
206
241
218
205
241
233
194
239
258
244
267
339
224
205
242
202
260
275
173
243
178
228
251
242
239
231
203
249
277
215
202
169
243
258
208
306
232
231
211
224
249
256
203
...

result:

ok 1797 numbers

Test #70:

score: 0
Wrong Answer
time: 410ms
memory: 23412kb

input:

59284 89368 1930
4029 716
1741 4029
14542 4029
48937 4029
716 24494
29506 1741
4029 3097
2898 716
3097 8627
2898 46025
29506 15319
716 12015
1741 5566
8627 58178
2898 14837
7742 1741
21507 24494
20151 24494
48937 9926
55162 7742
32033 14837
2898 27435
12292 8627
24972 58178
55074 48937
45787 21507
1...

output:

369
311
313
353
339
335
284
364
434
382
298
243
268
306
282
383
400
371
343
357
399
329
285
264
350
350
372
391
378
398
281
257
419
308
307
462
379
357
327
356
323
427
360
368
312
394
268
310
310
324
275
312
279
347
298
281
314
291
447
257
320
269
343
311
397
279
332
319
238
268
369
334
301
321
390
...

result:

wrong answer 1276th numbers differ - expected: '289', found: '59'

Subtask #5:

score: 0
Wrong Answer

Test #102:

score: 0
Wrong Answer
time: 665ms
memory: 25452kb

input:

55965 89652 95687
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26...

output:

26865
1
39914
17122
9941
18973
1
29300
18235
1
7705
14588
18168
10437
9845
1360
16279
8161
21883
12817
30989
3100
13902
35077
12908
21200
43577
1
1
4016
9221
1
6526
1
23259
6647
36075
10314
5128
41081
15838
1197
41166
24623
1
18786
29659
8809
42423
26355
30971
28924
1
24798
616
10947
38023
25288
339...

result:

wrong answer 1st numbers differ - expected: '42788', found: '26865'

Subtask #6:

score: 0
Skipped

Dependency #1:

0%