QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#933564#6340. Tourismsunkaihuan0 654ms18980kbC++142.1kb2025-03-13 20:54:332025-03-13 20:54:41

Judging History

This is the latest submission verdict.

  • [2025-03-13 20:54:41]
  • Judged
  • Verdict: 0
  • Time: 654ms
  • Memory: 18980kb
  • [2025-03-13 20:54:33]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct seg{
    int l,r;mutable int v;
    bool operator<(const seg &a)const{return l<a.l;}
};set<seg> s;
#define it set<seg>::iterator
vector<pair<int,int> > ql[N];
vector<int> to[N];
int fa[N],d[N],sz[N],son[N];
int dfn[N],tp[N],num;
int n,m,q,p[N],c[N],an[N];

void add(int x,int v){for(;x<=n;x+=x&-x)c[x]+=v;}
int ask(int x){int r=0;for(;x;x-=x&-x)r+=c[x];return r;}

void dfs1(int x,int f){
    fa[x]=f,d[x]=d[f]+1,sz[x]=1;
    for(auto j:to[x]){
        if(j==f)continue;dfs1(j,x);
        if(sz[son[x]]<sz[j])son[x]=j;
        sz[x]+=sz[j];
    }
}

void dfs2(int x,int f){
    dfn[x]=++num,tp[x]=f;
    if(son[x])dfs2(son[x],f);
    for(auto j:to[x])
        if(j!=fa[x]&&j!=son[x])dfs2(j,j);
}

it in(int l,int r,int w){add(w,r-l+1);return s.insert({l,r,w}).first;}
void de(int l,int r,int w){add(w,-r+l-1),s.erase({l,r,w});}

it split(int x){
    it pl=s.lower_bound({x,-1,0});
    if(pl!=s.end()&&pl->l==x)return pl;
    pl--;if(pl->r<x)return s.end();
    int l=pl->l,r=pl->r,v=pl->v;assert(l<x&&r>=x);
    de(l,r,v);in(l,x-1,v);return in(x,r,v);
}

void ins(int l,int r,int w){
    if(s.size()){
    it itr=split(r+1),itl=split(l),t;
    for(it pl=itl;pl!=itr;)t=pl,assert(t!=s.end()),pl++,de(t->l,t->r,t->v);
    }in(l,r,w);
}

int main(){
    // ios::sync_with_stdio(false);
    // cin.tie(0); cout.tie(0);
    cin>>n>>m>>q; int x,y;
    for(int i=1;i<n;i++)cin>>x>>y,
        to[x].push_back(y),to[y].push_back(x);
    dfs1(1,0);dfs2(1,1);
    for(int i=1;i<=m;i++)cin>>p[i];
    for(int i=1;i<=q;i++)
        cin>>x>>y,ql[y].push_back({x,i});ins(1,n,1);
    for(int i=1;i<=m;i++){
        if(i>1){
            x=p[i-1],y=p[i];
            while(tp[x]!=tp[y]){
                if(d[tp[x]]<d[tp[y]])swap(x,y);
                ins(dfn[tp[x]],dfn[x],i),x=fa[tp[x]];
            }if(d[x]<d[y])swap(x,y);
            ins(dfn[y],dfn[x],i);
        }for(auto j:ql[i])
            an[j.second]=(j.first==i?1:n-ask(j.first));
    }for(int i=1;i<=q;i++)cout<<an[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: 1ms
memory: 11388kb

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
97
110
93
110
139
101
24
126
121
70
97
83
96
25
113
86
60
101
49
107
131
66
33
4
114
86
110
59
123
46
130
73
114
93
88
113
85
25
95
127
69
85
121
77
127
123
83
34
114
99
121
63
56
99
106
103
69
127
48
74
134
95
94
22
120
105
116
36
83
124
112
130
112
34
112
138
114
98
64
122
109
1
105
137
73
105
...

result:

wrong answer 7th numbers differ - expected: '84', found: '101'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #56:

score: 0
Wrong Answer
time: 121ms
memory: 18980kb

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
55319
55313
55306
55319
53676
55320
55321
55319
55319
55321
55319
55318
55320
55311
55311
55319
55321
55321
55319
55319
55317
55320
55319
55319
55318
55321
55318
55319
55319
55319
55321
55319
55320
55319
55319
55319
55319
55319
55319
55320
55321
55319
55186
55204
55320
55319
55319
55297
55318
...

result:

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

Subtask #4:

score: 0
Wrong Answer

Test #69:

score: 18
Accepted
time: 261ms
memory: 14828kb

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: 403ms
memory: 15664kb

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 1277th numbers differ - expected: '354', found: '638'

Subtask #5:

score: 0
Wrong Answer

Test #102:

score: 0
Wrong Answer
time: 654ms
memory: 17976kb

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:

42788
12806
39914
18090
47411
43990
55965
29300
18235
31075
44208
47526
32163
44460
32385
30155
45741
45708
47396
43518
30989
19208
13902
35077
49210
21200
43577
55965
55965
35461
45079
55965
42233
55965
23259
44558
41924
39465
34626
41081
32139
34482
41166
24623
55965
18786
29659
38064
42423
42321
...

result:

wrong answer 2nd numbers differ - expected: '7820', found: '12806'

Subtask #6:

score: 0
Skipped

Dependency #1:

0%