| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 954454 |
2024-03-28T01:07:33 Z |
owoovo |
Tourism (JOI23_tourism) |
C++17 |
|
1 ms |
4444 KB |
#include<bits/stdc++.h>
#define ll long long
#define MP make_pair
#define F first
#define S second
using namespace std;
int f[100010],si[100010],hs[100010],top[100010],dep[100010],in[100010],cnt;
int n,m,q;
vector<int> e[100010];
int dfs1(int now,int last){
dep[now]=dep[last]+1;
f[now]=last;
si[now]=1;
for(auto x:e[now]){
if(x==last)continue;
int siz=dfs1(x,now);
if(siz>si[hs[now]]){
hs[now]=x;
}
si[now]+=siz;
}
return si[now];
}
void dfs2(int now,int tp){
in[now]=++cnt;
top[now]=tp;
if(hs[now]!=0)dfs2(hs[now],tp);
for(auto x:e[now]){
if(x==f[now]||x==hs[now])continue;
dfs2(x,x);
}
return;
}
struct Bit{
int ori[100010]={};
void modify(int p,int x){
if(p==0)return ;
while(p<=100000){
ori[p]+=x;
p+=p&(-p);
}
return ;
}
int query(int p){
int ans=0;
while(p){
ans+=ori[p];
p-=p&(-p);
}
return ans;
}
}bit;
int ans[100010],ver[100010];
vector<pair<pair<int,int>,int>> qu;
map<int,int> s;
void segin(int l,int r,int x){
if(l>r)swap(l,r);
auto lit = s.upper_bound(l);
lit = prev(lit);
int fl = lit->first;
int fv = lit->second;
int pv = 0;
while(lit->first<=r){
pv = lit->second;
bit.modify(lit->second,-(next(lit)->first-lit->first));
auto k = lit;
++lit;
s.erase(k);
}
bit.modify(x,r-l+1);
bit.modify(fv,l-fl);
if(lit->first!=r+1){
s[r+1] = pv;
bit.modify(pv,lit->first-r);
}
s[fl] = fv;
s[l] = x;
}
void putin(int u,int v,int id){
while(1){
//cout<<u<<" "<<v<<" "<<id<<"\n";
if(top[u]==top[v]){
segin(in[v],in[u],id);
break;
}
if(dep[top[u]]<dep[top[v]])swap(u,v);
segin(in[top[u]],in[u],id);
u=f[top[u]];
}
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m>>q;
s[1]=0;
s[n+1]=0;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(1,1);
dfs2(1,1);
for(int i=1;i<=m;i++){
cin>>ver[i];
}
for(int i=1;i<=q;i++){
int l,r;
cin>>l>>r;
if(l==r){
ans[i]=1;
continue;
}
qu.push_back({{l,r},i});
}
sort(qu.begin(),qu.end());
reverse(qu.begin(),qu.end());
int now=0;
for(int i=m-1;i>=1;i--){
//cout<<i<<"ok\n";
//put in i,i+1
putin(ver[i],ver[i+1],i+1);
while(now!=q&&qu[now].F.F==i){
auto [x,id]=qu[now];
auto [l,r]=x;
ans[id]=bit.query(r);
now++;
}
}
for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
