QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#667976#6340. TourismL_Hospital_#0 189ms62000kbC++143.1kb2024-10-23 10:18:362024-10-23 10:18:43

Judging History

你现在查看的是最新测评结果

  • [2024-10-23 10:18:43]
  • 评测
  • 测评结果:0
  • 用时:189ms
  • 内存:62000kb
  • [2024-10-23 10:18:36]
  • 提交

answer

#include<bits/stdc++.h>
# define rep(i, j, k) for (int i = j; i <= k; ++i)
using namespace std;

int n, m, qu, c[100005], hd[100005], to[200005], nxt[200005], etimer;
int p[100005], d[100005], sz[100005], son[100005], t1[100005], t2[100005], top[100005], id[100005], timer;
int lg2[100005], minn[20][100005], maxx[20][100005];
int ans[100005];
struct node
{
    int pos, num;
    bool operator<(const node &x)const{return pos < x.pos;}
};
vector < node > aff[100005];
struct oper
{
    int l, r, pos, id, num;
    bool operator<(const oper &x)const{return pos < x.pos || pos == x.pos && id < x.id;}
} q[2000005];
node stk[2000005];
int r, nu;
int bit[100005];
void addedge(int u, int v){to[++etimer] = v, nxt[etimer] = hd[u], hd[u] = etimer;}
void dfs_pre(int u, int fa)
{
    d[u] = d[p[u] = fa] + 1, sz[u] = 1;
    for (int i = hd[u]; i; i = nxt[i]) if (to[i] != fa) {dfs_pre(to[i], u); sz[u] += sz[to[i]]; if (sz[son[u]] < sz[to[i]]) son[u] = to[i];}
}
void dfs(int u)
{
    t1[u] = ++timer, id[timer] = u; top[u] = (u == son[p[u]] ? top[p[u]] : u);
    if (son[u]) dfs(son[u]);
    for (int i = hd[u]; i; i = nxt[i]) if (to[i] != p[u] && to[i] != son[u]) dfs(to[i]);
    t2[u] = timer;
}
int lca(int u, int v){while (top[u] != top[v]) if (d[top[u]] < d[top[v]]) v = p[top[v]]; else u = p[top[u]]; return d[u] < d[v] ? u : v;}
void buildst()
{
    lg2[0] = -1;
    rep(i, 1, n) lg2[i] = lg2[i >> 1] + 1, minn[0][i] = maxx[0][i] = t1[c[i]];
    rep(p, 1, 17) rep(i, 1, n - (1 << p) + 1) minn[p][i] = min(minn[p - 1][i], minn[p - 1][i + (1 << (p - 1))]), maxx[p][i] = max(maxx[p - 1][i], maxx[p - 1][i + (1 << (p - 1))]);
}
int la(int l, int r)
{
    int lg = lg2[r - l + 1];
    return lca(id[min(minn[lg][l], minn[lg][r - (1 << lg) + 1])], id[max(maxx[lg][l], maxx[lg][r - (1 << lg) + 1])]);
}
void deal(int pos, int u)
{
    while (u) aff[top[u]].push_back({pos, d[u] - d[top[u]] + 1}), u = p[top[u]];
}
void add(int x, int num){for (; x <= m; x += (x & (-x))) bit[x] += num;}
int query(int x){int ans = 0; for (; x; x &= (x - 1)) ans += bit[x]; return ans;}
signed main()
{
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	cin >> n >> m >> qu, nu = qu;
	rep(i, 1, n - 1) {int u, v; cin >> u >> v; addedge(u, v), addedge(v, u);}
	dfs_pre(1, 0), dfs(1);
	rep(i, 1, m) cin >> c[i], deal(i, c[i]);
	buildst();
	rep(i, 1, qu) cin >> q[i].l >> q[i].r, q[i].pos = q[i].r, q[i].id = i;
	rep(i, 1, n) if (!aff[i].empty())
	{
        sort(aff[i].begin(), aff[i].end());
        r = 0;
        for (int j = 0; j < aff[i].size(); ++j)
        {
            q[++nu] = (oper) {stk[r].pos + 1, aff[i][j].pos, aff[i][j].pos, 0, aff[i][j].num};
            while (r && stk[r].num < aff[i][j].num) q[++nu] = {stk[r - 1].pos + 1, stk[r].pos, aff[i][j].pos, 0, aff[i][j].num - stk[r].num}, --r;
            stk[++r] = aff[i][j];
        }
	}
	sort(q + 1, q + nu + 1);
	rep(i, 1, nu) {if (!q[i].id) add(q[i].l, q[i].num), add(q[i].r + 1, -q[i].num); else ans[q[i].id] = query(q[i].l) - d[la(q[i].l, q[i].r)] + 1;}
	rep(i, 1, qu) cout << 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: 24160kb

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
99
112
93
110
141
86
24
128
123
70
99
85
96
25
113
86
60
81
49
109
133
66
33
11
43
88
112
62
125
46
132
73
65
93
77
115
85
25
95
129
69
85
123
79
129
125
85
34
64
99
121
63
56
101
108
33
69
129
48
76
136
70
96
22
120
105
118
36
85
126
114
132
25
34
114
140
39
98
66
122
111
3
105
139
73
105
111
91...

result:

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

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #56:

score: 0
Wrong Answer
time: 49ms
memory: 35804kb

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:

55321
55322
55313
55306
55319
53676
55322
55306
55322
55322
55288
55322
55318
55322
55311
55311
55322
55302
55306
55319
55322
55317
55322
55319
55322
55318
55300
55318
55322
55322
55322
55281
55319
55322
55322
55322
55322
55322
55322
55322
55322
55306
55322
55186
55204
55322
55322
55319
55297
55321
...

result:

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

Subtask #4:

score: 0
Wrong Answer

Test #69:

score: 18
Accepted
time: 63ms
memory: 39140kb

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: 115ms
memory: 47372kb

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: '293'

Subtask #5:

score: 0
Wrong Answer

Test #102:

score: 0
Wrong Answer
time: 189ms
memory: 62000kb

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:

42789
7821
39914
18091
47412
43991
2172
29300
18235
16452
44209
47527
32164
44461
32386
30156
45742
45709
47397
43519
30989
19209
13902
35077
49211
21200
43577
32111
19691
35462
45080
11602
42234
16863
23259
44559
41925
39466
34627
41081
32140
34483
41166
24623
11639
18786
29659
38065
42423
42322
30...

result:

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

Subtask #6:

score: 0
Skipped

Dependency #1:

0%