Submission #998829

#	Time	Username	Problem	Language	Result	Execution time	Memory
998829		imarn	Tourism (JOI23_tourism)	C++14	28 / 100	5069 ms	21988 KiB

tourism

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
using namespace std;
const int mxn=1e5+5,blc=505;
vector<int>g[mxn];
int tin[mxn],tout[mxn],cnt=0,pr[mxn][19],d[mxn]{0};
void dfs(int u,int p,int l){
    d[u]=l;pr[u][0]=p;tin[u]=++cnt;
    for(int i=1;i<19;i++)pr[u][i]=pr[pr[u][i-1]][i-1];
    for(auto v:g[u]){
        if(v==p)continue;dfs(v,u,l+1);
    }tout[u]=cnt;
}
int get(int a,int b){
    if(d[a]>d[b])swap(a,b);
    for(int i=18;i>=0;i--)if(d[b]-(1<<i)>=d[a])b=pr[b][i];
    if(a==b)return a;
    for(int i=18;i>=0;i--)if(pr[a][i]!=pr[b][i])a=pr[a][i],b=pr[b][i];
    return pr[a][0];
}
bool cmp(pair<pii,int>a,pair<pii,int>b){
    if(a.f.f/blc==b.f.f/blc)return a.f.s<b.f.s;
    else return a.f.f<b.f.f;
}multiset<pii>ms;
int ans=0;
int cal(int a,int b){
    return d[a]+d[b]-2*d[get(a,b)];
}
void add(int t,int u){
    if(ms.empty()){ms.insert({t,u});return;}
    if(ms.size()==1){
        ms.insert({t,u});
        ans += 2*(cal(ms.begin()->s,(--ms.end())->s));
        return;
    }
    if(t>=(--ms.end())->f||t<=ms.begin()->f){
        ans-=cal(ms.begin()->s,(--ms.end())->s);
        ans+=cal(ms.begin()->s,u);
        ans+=cal((--ms.end())->s,u);
        ms.insert({t,u});
        return;
    }
    ms.insert({t,u});
    auto it = ms.lower_bound({t,u});
    auto it2=++it;it--;auto it3=--it;it++;
    ans-=cal(it2->s,it3->s);
    ans+=cal(it2->s,it->s);
    ans+=cal(it3->s,it->s);
}
void del(int t,int u){
    if(ms.size()==1){
        ms.erase({t,u});return;
    }
    if(ms.size()==2){
        ans-=2*(cal(ms.begin()->s,(--ms.end())->s));
        ms.erase(ms.lower_bound({t,u}));return;
    }auto it = ms.lower_bound({t,u});
    if(it==ms.begin()){
        ans-=cal(it->s,(--ms.end())->s);
        ans-=cal(it->s,next(it)->s);
        ans+=cal(next(it)->s,(--ms.end())->s);
        ms.erase(ms.lower_bound({t,u}));return;
    }
    if(it==(--ms.end())){
        ans-=cal(it->s,prev(--ms.end())->s);
        ans-=cal(it->s,ms.begin()->s);
        ans+=cal(ms.begin()->s,prev(--ms.end())->s);
        ms.erase(ms.lower_bound({t,u}));return;
    }auto it2=--it;it++;auto it3=++it;it--;
    ans-=cal(it2->s,it->s);ans-=cal(it3->s,it->s);
    ans+=cal(it2->s,it3->s);ms.erase(ms.lower_bound({t,u}));

}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m,q;cin>>n>>m>>q;
    for(int i=1;i<=n-1;i++){
        int u,v;cin>>u>>v;g[u].pb(v),g[v].pb(u);
    }dfs(1,1,0);int a[m+1];vector<pair<pii,int>>qr(q);
    for(int i=1;i<=m;i++)cin>>a[i];
    for(int i=0;i<q;i++)cin>>qr[i].f.f>>qr[i].f.s,qr[i].s=i;
    sort(qr.begin(),qr.end(),cmp);int res[q];
    int cl=1,cr=0;
    for(auto it : qr){
        while(cr<it.f.s)cr++,add(tin[a[cr]],a[cr]);
        while(cl>it.f.f)cl--,add(tin[a[cl]],a[cl]);
        while(cr>it.f.s)del(tin[a[cr]],a[cr]),cr--;
        while(cl<it.f.f)del(tin[a[cl]],a[cl]),cl++;
        res[it.s]=ans/2+1;
    }for(int i=0;i<q;i++)cout<<res[i]<<'\n';
}

Compilation message (stderr)

tourism.cpp: In function 'void dfs(int, int, int)':
tourism.cpp:23:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   23 |         if(v==p)continue;dfs(v,u,l+1);
      |         ^~
tourism.cpp:23:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   23 |         if(v==p)continue;dfs(v,u,l+1);
      |                          ^~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 7
• Subtask 4: 18 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41