QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#933519 | #6340. Tourism | sunkaihuan | 0 | 64ms | 19352kb | C++14 | 2.2kb | 2025-03-13 19:53:56 | 2025-03-13 19:53:56 |
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);
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: 64ms
memory: 19352kb
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 2 54709 34350 48700 50519 0 0 2 17 0 0 22711 0 23222 48039 29 0 0 47943 38676 51647 0 46597 0 54602 0 32970 2 2 47984 0 45538 0 2 2 17 2 2 0 0 0 2 40393 39969 0 51809 33139 37824 43541 2 43603 53572 0 40738 17 0 0 0 44057 46836 54319 44703 36208 0 50225 0 34241 17 49653 54739 0 0 50531 0 0 0 53879...
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%