QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#933524#6340. Tourismsunkaihuan0 411ms18988kbC++142.2kb2025-03-13 19:59:002025-03-13 19:59:00

Judging History

This is the latest submission verdict.

  • [2025-03-13 19:59:00]
  • Judged
  • Verdict: 0
  • Time: 411ms
  • Memory: 18988kb
  • [2025-03-13 19:59:00]
  • 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;x-=x&-x)c[x]+=v;}
int ask(int x){int r=0;for(;x<=n;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){
    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});s.insert({1,n,0});
    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]])
                    ins(dfn[tp[y]],dfn[y],i),y=fa[tp[y]];
                else ins(dfn[tp[x]],dfn[x],i-1),x=fa[tp[x]];
            }if(d[x]<d[y])ins(dfn[x],dfn[y],i),p[i]=x;
            else{
                if(x!=y)ins(dfn[y]+1,dfn[x],i-1);
                ins(dfn[y],dfn[y],i);p[i]=y;
            }
        }for(auto j:ql[i])
            an[j.second]=(j.first==i?1:ask(j.first));
    }for(int i=1;i<=q;i++)cout<<an[i]<<"\n";
    return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 11356kb

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
39
110
93
110
139
0
27
126
121
70
97
83
96
25
113
86
60
0
49
107
131
66
33
9
0
86
110
60
123
46
130
73
0
93
0
113
85
25
95
127
69
85
121
77
127
123
83
34
0
99
121
63
59
99
106
0
69
127
51
74
134
0
94
27
120
105
116
36
30
124
112
130
0
34
112
138
0
98
39
122
109
1
105
137
73
105
109
89
95
31
120
1...

result:

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

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #56:

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

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:

0
16
55316
55306
55319
54811
1
0
16
16
0
0
55318
1
55311
55311
87
0
0
55319
55319
55317
1
55319
0
55318
0
55318
16
16
55319
0
55319
1
16
16
16
16
16
0
1
0
16
55211
55204
0
55319
55319
55309
55318
16
55318
55319
0
55319
16
0
0
1
55319
55318
55318
55293
55319
1
55319
0
55317
16
55319
55319
1
0
55309
1...

result:

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

Subtask #4:

score: 0
Wrong Answer

Test #69:

score: 0
Wrong Answer
time: 154ms
memory: 15604kb

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
239
199
215
294
241
233
267
184
241
208
241
257
226
216
222
192
270
221
242
287
226
216
252
273
204
282
187
259
195
154
185
207
242
218
205
241
233
195
240
259
245
269
339
224
206
242
202
261
276
174
243
178
229
251
243
239
231
204
250
278
215
203
170
244
258
210
307
232
232
211
224
249
256
204
...

result:

wrong answer 2nd numbers differ - expected: '238', found: '239'

Subtask #5:

score: 0
Wrong Answer

Test #102:

score: 0
Wrong Answer
time: 411ms
memory: 18352kb

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
0
39914
18090
14936
32970
0
29300
18235
0
13086
21803
32163
16999
28245
2515
25805
13125
35238
21406
30989
5677
13902
35077
18388
21200
43577
0
0
12145
14861
0
12237
0
23259
11450
41924
20100
14626
41081
32139
2053
41166
24623
0
18786
29659
18499
42423
42321
30971
28924
0
25952
1194
16277
3802...

result:

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

Subtask #6:

score: 0
Skipped

Dependency #1:

0%