Submission #834226

#	Time	Username	Problem	Language	Result	Execution time	Memory
834226		alvingogo	Tourism (JOI23_tourism)	C++14	100 / 100	286 ms	89696 KiB

tourism

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

struct BIT{
    int n;
    vector<int> bt;
    void init(int x){
        n=x;
        bt.resize(n+1);
    }
    void update(int x,int y){
        x++;
        for(;x<=n;x+=(x&-x)){
            bt[x]+=y;
        }
    }
    int query(int x){
        int ans=0;
        x++;
        for(;x>0;x-=(x&-x)){
            ans+=bt[x];
        }
        return ans;
    }
    int sum(int l,int r){
        return query(r)-(l==0?0:query(l-1));
    }
}bt;
struct SZT{
    vector<vector<int> > dg;
    void init(vector<int>& x){
        int f=x.size();
        int r=__lg(f)+1;
        dg.resize(r,vector<int>(f));
        dg[0]=x;
        for(int i=1;i<r;i++){
            for(int j=0;j+(1<<(i))-1<f;j++){
                dg[i][j]=min(dg[i-1][j],dg[i-1][j+(1<<(i-1))]);
            }
        }
    }
    int query(int l,int r){
        int t=__lg(r-l+1);
        return min(dg[t][l],dg[t][r-(1<<(t))+1]);
    }
}pd,lin,lout;
struct ST{
    vector<int> st;
    void init(int x){
        st.resize(4*x);
    }
    void update(int v,int L,int R,int p,int x){
        if(L==R){
            st[v]=x;
            return;
        }  
        int m=(L+R)/2;
        if(p<=m){
            update(2*v+1,L,m,p,x);
        }
        else{
            update(2*v+2,m+1,R,p,x);
        }
        st[v]=max(st[2*v+1],st[2*v+2]);
    }
    int query(int v,int L,int R,int l,int r){
        if(L==l && r==R){
            return st[v];
        }
        int m=(L+R)/2;
        if(r<=m){
            return query(2*v+1,L,m,l,r);
        }
        else if(l>m){
            return query(2*v+2,m+1,R,l,r);
        }
        else{
            return max(query(2*v+1,L,m,l,m),query(2*v+2,m+1,R,m+1,r));
        }
    }
}po;
struct no{
    vector<int> ch;
    int dep=-1;
    int fa=-1;
    int vis=0;
    int in=-1,out=-1;
};
vector<no> v;
vector<int> z;
int cnt=0;
void dfs(int r,int f){
    v[r].fa=f;
    v[r].dep=v[f].dep+1;
    v[r].in=cnt;
    z.push_back(v[r].dep);
    cnt++;
    for(auto h:v[r].ch){
        if(h!=f){
            dfs(h,r);
            z.push_back(v[r].dep);
            cnt++;
        }
    }
    v[r].out=cnt-1;
}
int lca(int l,int r){
    int a=lin.query(l,r);
    int b=-lout.query(l,r);
    return pd.query(a,b);
}
signed main(){
    AquA;
    int n,m,q;
    cin >> n >> m >> q;
    v.resize(n);
    vector<int> c(n+1);
    c[0]=0;
    for(int i=1;i<n;i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        v[a].ch.push_back(b);
        v[b].ch.push_back(a);
    }
    dfs(0,0);
    pd.init(z);
    int g=z.size();
    vector<int> ii,oo;
    vector<int> w(m);
    for(int i=0;i<m;i++){
        int a;
        cin >> a;
        a--;
        w[i]=a;
        ii.push_back(v[a].in);
        oo.push_back(-v[a].out);
    }
    lin.init(ii);
    lout.init(oo);
    vector<vector<pair<int,int> > > vq(m);
    vector<int> ans(q);
    for(int i=0;i<q;i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        vq[b].push_back({i,a});
    }
    po.init(g);
    bt.init(m);
    vector<int> co(m);
    for(int i=0;i<m;i++){
        bt.update(i,v[w[i]].dep);
        int x=w[i];
        while(!v[x].vis){
            v[x].vis=1;
            if(x==0){
                break;
            }
            x=v[x].fa;
        }
        while(x!=0){
            int s=po.query(0,0,g-1,v[x].in,v[x].out);
            int z=co[s];
            bt.update(s,v[co[s]].dep-v[x].dep);
            co[s]=x;
            x=z;
        }
        co[i]=0;
        po.update(0,0,g-1,v[w[i]].in,i);
        for(auto [h,l]:vq[i]){
            ans[h]=bt.sum(l,i)-lca(l,i)+1;
        }
    }
    for(int i=0;i<q;i++){
        cout << ans[i] << "\n";
    }
    return 0;
}

Compilation message (stderr)

tourism.cpp: In function 'int main()':
tourism.cpp:179:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  179 |         for(auto [h,l]:vq[i]){
      |                  ^

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