Submission #1261229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261229		user736482	Tourism (JOI23_tourism)	C++20	100 / 100	1920 ms	93052 KiB

tourism

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000007
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
ll odp[100007];
pair<ll,ll> par[100007];
vector<pair<ll,ll>>g[100007],d[100007];
vector<pair<pair<ll,ll>,ll>>ak,ak2;
bool czy[100007],czy2[100007];
ll mn[100007];
ll mx[100007];

ll sg[POT];

void add(ll v,ll pocz,ll kon,ll l,ll r,ll x){
    if(l>kon || r<pocz)return;
    if(kon>=r && pocz<=l)sg[v]+=x;
    else{
        add(v*2,pocz,kon,l,(l+r)/2,x);
        add(v*2+1,pocz,kon,(l+r)/2+1,r,x);
    }
}

ll gt(ll v){
    v+=POT/2-1;
    ll ans=0;
    while(v){
        ans+=sg[v];
        v/=2;
    }
    return ans;
}
void dfs3(ll v,ll pop,ll x){
    //  cout<<v<<" "<<czy[v]<<"  "<<flush;
    par[v]={pop,x};
    ll cnt=0;
    ll x2=0;
    for(auto i : g[v]){
        if(i.ff!=pop){
            d[v].pb(i);
            dfs3(i.ff,v,i.ss);
            if(czy2[i.ff]){
                cnt++;
            }
        }
    }
    
    if(cnt>1)czy[v]=1;
    if(czy[v] || cnt>0)czy2[v]=1;
    else czy2[v]=0;
    //cout<<v<<" "<<czy[v]<<"\n"<<flush;

    return;
}
void dfs4(ll v,ll pop,ll x){
    //  cout<<v<<" "<<czy[v]<<"  "<<flush;
    par[v]={pop,x};
    ll cnt=0;
    ll x2=0;
    for(auto i : g[v]){
        if(i.ff!=pop){
            dfs4(i.ff,v,i.ss);
        }
    }
    
    //cout<<v<<" "<<czy[v]<<"\n"<<flush;
    if(czy[v] && v!=pop){
        ll x3=par[v].ss;
        ll pom=par[v].ff;
        while(!czy[pom]){
            x3+=par[pom].ss;
            pom=par[pom].ff;
        }
        ak.pb({{pom,v},x3});
    }

    return;
}
void dfs(ll v,ll pop,ll x){
  dfs3(v,pop,x);dfs4(v,pop,x);
}

void dfs2(ll v,ll x){
    for(auto i : d[v]){
        dfs2(i.ff,i.ss);
        mn[v]=min(mn[v],mn[i.ff]);
        mx[v]=max(mx[v],mx[i.ff]);
    }
    ak.pb({{mx[v],mn[v]},x});
}

void solve(vector<pair<pair<ll,ll>,ll>>e,ll n,vector<pair<pair<ll,ll>,ll>>zap,vector<ll>arr){
   // for(ll i=1;i<POT;i++)sg[i]=0;
   /* cout<<n<<"\n"<<flush;
    for(auto i : e){
        cout<<i.ff.ff<<" "<<i.ff.ss<<" "<<i.ss<<"\n"<<flush;
    }
    cout<<"\n"<<flush;
    for(auto i :zap){
        cout<<i.ff.ff<<" "<<i.ff.ss<<" "<<i.ss<<"\n"<<flush;
    }
    cout<<"\n"<<flush;
    for(ll i : arr)cout<<i<<" ";
    cout<<"\n\n\n"<<flush;*/
    ak.clear();
    for(ll i=1;i<=n;i++){g[i].clear();czy[i]=0;d[i].clear();}
    for(auto i : e){
        g[i.ff.ff].pb({i.ff.ss,i.ss});
        g[i.ff.ss].pb({i.ff.ff,i.ss});
    }
    ll md=arr.size()/2;
    for(ll i : arr)czy[i]=1;
    dfs(arr[md],arr[md],0);
   /* for(auto i : ak){
        cout<<i.ff.ff<<" "<<i.ff.ss<<" "<<i.ss<<"\n"<<flush;
    }
    cout<<"\n"<<flush;*/
    for(ll i=1;i<=n;i++){g[i].clear();czy[i]=0;d[i].clear();}
    ll pm=1;
    map<ll,ll>sk;
    ak2.clear();
    swap(ak,ak2);
    for(auto i : ak2){
        if(sk[i.ff.ff]==0)sk[i.ff.ff]=pm++;
        if(sk[i.ff.ss]==0)sk[i.ff.ss]=pm++;
        ak.pb({{sk[i.ff.ff],sk[i.ff.ss]},i.ss});
    }
    
  /*  for(auto i : ak){
        cout<<i.ff.ff<<" "<<i.ff.ss<<" "<<i.ss<<"\n"<<flush;
    }
    cout<<"\n"<<flush;
    cout<<pm<<" ";*/
    n=pm-1;
    for(ll i=0;i<arr.size();i++)arr[i]=sk[arr[i]];
    for(ll i : arr)czy[i]=1;
   // cout<<"\n"<<flush;
   // for(ll i : arr)cout<<i<<" ";cout<<"\n"<<flush;
    for(ll i=1;i<=n;i++){
        mn[i]=INFL;
        mx[i]=-1;
    }
    for(auto i : ak){
        g[i.ff.ff].pb({i.ff.ss,i.ss});
        g[i.ff.ss].pb({i.ff.ff,i.ss});
    }
     auto akk=ak;
  //   cout<<"xd"<<flush;
    dfs(arr[md],arr[md],0);
  /*  cout<<"xd"<<flush;
    for(ll i=1;i<=n;i++){
        cout<<i<<": ";
        for(auto j : d[i])cout<<j.ff<<" "<<j.ss<<"   ";
        cout<<"\n"<<flush;
    }
        */
    for(ll i=0;i<md;i++){
        mx[arr[i]]=i;
    }
    for(ll i=md+1;i<arr.size();i++)mn[arr[i]]=min(mn[arr[i]],i);
    ak.clear();
    dfs2(arr[md],0);
    vector<pair<pair<ll,ll>,ll>>moj,lewe,prawe;
    for(auto i : zap){
        
        if(i.ff.ss<=md)lewe.pb(i);
        else if(i.ff.ff>md+1)prawe.pb(i);
        else {moj.pb(i);moj.back().ff.ss*=-1;}
    }
    for(ll i=0;i<prawe.size();i++){
        prawe[i].ff.ff-=(md+1);
        prawe[i].ff.ss-=(md+1);
    }
   // cout<<"\n"<<flush;
  //  for(ll i=1;i<=n;i++){
   //     cout<<mn[i]<<" "<<mx[i]<<"\n"<<flush;
  //  }
    
    vector<pair<ll,ll>>op;
    for(auto i : ak){
        op.pb({POT/2,-i.ss});
        op.pb({i.ff.ss,i.ss});
        moj.pb({{0,POT/2},i.ss});
        moj.pb({{i.ff.ff+1,i.ff.ss},-i.ss});
    }
    sort(moj.begin(),moj.end());
    for(auto i : moj){
       // cout<<i.ff.ff<<" "<<i.ff.ss<<" "<<i.ss<<"\n"<<flush;
        if(i.ff.ss>=0){
            
            add(1,1,i.ff.ss,1,POT/2,i.ss);
        }
        else{
            i.ff.ss*=-1;
            odp[i.ss]=gt(i.ff.ss);
         //   cout<<odp[i.ss]<<" ";
        }
    }
    for(auto i : op){
        add(1,1,i.ff,1,POT/2,i.ss);
    }
    
    vector<ll>a1,a2;
    for(ll i=0;i<md;i++)a1.pb(arr[i]);
    for(ll i=md+1;i<arr.size();i++)a2.pb(arr[i]);
    //cout<<md<<" "<<a1.size()<<" a "<<a2.size()<<"\n"<<flush;
   
    if(a1.size()){
     //   cout<<"lw: ";
    
    solve(akk,n,lewe,a1);}
    if(a2.size()){//cout<<"pw: ";
    solve(akk,n,prawe,a2);}
    //cout<<"back";
}

ll n,m,q;
vector<pair<pair<ll,ll>,ll>>e;
vector<ll>arr;
vector<pair<pair<ll,ll>,ll>>zap;
int main(){
    cin>>n>>m>>q;
    ll a,b;
    for(ll i=0;i<n-1;i++){
        cin>>a>>b;
        e.pb({{a,b},1});
    }
    for(ll i=0;i<m;i++){
        cin>>a;
        arr.pb(a);
    }
    for(ll i=0;i<q;i++){
        cin>>a>>b;
        zap.pb({{a,b},i});
    }
    solve(e,n,zap,arr);
    for(ll i=0;i<q;i++)cout<<odp[i]+1<<"\n"<<flush;
}   

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