QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#933564 | #6340. Tourism | sunkaihuan | 0 | 654ms | 18980kb | C++14 | 2.1kb | 2025-03-13 20:54:33 | 2025-03-13 20:54:41 |
Judging History
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%