QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#933520 | #6340. Tourism | sunkaihuan | 0 | 43ms | 19516kb | C++14 | 2.2kb | 2025-03-13 19:55:37 | 2025-03-13 19:55:37 |
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;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;
if(pl->r<x)return s.end();pl--;
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;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
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:
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #56:
score: 0
Wrong Answer
time: 43ms
memory: 19516kb
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 0 23629 34350 33768 51654 0 0 0 0 0 0 22711 0 23221 32860 0 0 0 40718 22386 51647 0 46596 0 54599 0 19565 0 0 20694 0 40168 0 0 0 0 0 0 0 0 0 0 40417 39968 0 19665 24034 9890 43541 0 5975 14665 0 40738 0 0 0 0 44057 35928 29217 22649 36207 0 4308 0 34241 0 49653 54737 0 0 38844 0 0 0 22083 17927 0...
result:
wrong answer 1st numbers differ - expected: '55319', found: '0'
Subtask #4:
score: 0
Runtime Error
Test #69:
score: 0
Runtime Error
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:
result:
Subtask #5:
score: 0
Runtime Error
Test #102:
score: 0
Runtime Error
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:
result:
Subtask #6:
score: 0
Skipped
Dependency #1:
0%