Submission #1191748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191748		AlgorithmWarrior	Escape Route 2 (JOI24_escape2)	C++20	100 / 100	1492 ms	136716 KiB

Main

#include <bits/stdc++.h>
#define pii pair<int,int>
#define ff first
#define ss second

using namespace std;

int const BLOCKSIZE=43;
long long const INF=1e18;
int const MAX=100005;
int const LOG=20;
int n,t;
int nrd[MAX];
vector<pii>drum[MAX];
int ln[MAX],rn[MAX];
int tata[MAX];
long long spn[MAX],spm[MAX];
vector<int>sons[MAX];
int lift[MAX][LOG];
vector<long long>dist[MAX];
long long dp[MAX];

void read(){
    cin>>n>>t;
    int i,j;
    for(i=1;i<n;++i){
        cin>>nrd[i];
        ln[i]=rn[i-1]+1;
        rn[i]=ln[i]+nrd[i]-1;
        for(j=0;j<nrd[i];++j){
            int a,b;
            cin>>a>>b;
            drum[i].push_back({a,b});
        }
        sort(drum[i].begin(),drum[i].end());
    }
}

void create_forest(){
    int i,j;
    for(i=1;i<=n-2;++i){
        vector<int>best;
        best.resize(nrd[i+1]);
        best[nrd[i+1]-1]=nrd[i+1]-1;
        for(j=nrd[i+1]-2;j>=0;--j)
            if(drum[i+1][j].ss<drum[i+1][best[j+1]].ss)
                best[j]=j;
            else
                best[j]=best[j+1];
        for(j=0;j<nrd[i];++j){
            auto it=lower_bound(drum[i+1].begin(),drum[i+1].end(),make_pair(drum[i][j].ss,0));
            if(it==drum[i+1].end()){
                tata[ln[i]+j]=ln[i+1]+best[0];
                sons[ln[i+1]+best[0]].push_back(ln[i]+j);
                spm[ln[i]+j]=t-drum[i][j].ss+drum[i+1][best[0]].ff;
            }
            else{
                int id=it-drum[i+1].begin();
                tata[ln[i]+j]=ln[i+1]+best[id];
                sons[ln[i+1]+best[id]].push_back(ln[i]+j);
                spm[ln[i]+j]=drum[i+1][best[id]].ff-drum[i][j].ss;
            }
        }
    }
    for(i=1;i<n;++i)
        for(j=0;j<nrd[i];++j)
            spn[ln[i]+j]=drum[i][j].ss-drum[i][j].ff;
}

void dfs(int nod){
    spm[nod]+=spn[tata[nod]];
    spn[nod]+=spm[nod];
    int i;
    lift[nod][0]=tata[nod];
    for(i=1;i<LOG;++i)
        lift[nod][i]=lift[lift[nod][i-1]][i-1];
    for(auto fiu : sons[nod])
        dfs(fiu);
}

void dfs_driver(){
    int i;
    for(i=ln[n-1];i<=rn[n-1];++i)
        dfs(i);
}

int anc(int nod,int h){
    int i;
    for(i=0;i<LOG;++i)
        if(h&(1<<i))
            nod=lift[nod][i];
    return nod;
}

void minself(long long& x,long long val){
    if(x>val)
        x=val;
}

long long solve(int st,int dest){
    long long ans=INF;
    int h=dest-st-1;
    int i;
    for(i=ln[st];i<=rn[st];++i){
        int stramos=anc(i,h);
        minself(ans,spn[i]-spm[stramos]);
    }
    return ans;
}

void dfs_init(int nod,int niv,int target){
    if(niv==target)
        dp[nod]=spn[nod];
    else{
        dp[nod]=INF;
        for(auto fiu : sons[nod]){
            dfs_init(fiu,niv-1,target);
            minself(dp[nod],dp[fiu]);
        }
    }
    minself(dist[target][niv+1],dp[nod]-spm[nod]);
}

void dfs_init_driver(){
    int i,j;
    for(i=1;i<n;++i)
        if(nrd[i]>BLOCKSIZE){
            dist[i].resize(n+5,INF);
            for(j=ln[n-1];j<=rn[n-1];++j)
                dfs_init(j,n-1,i);
        }
}

void process_queries(){
    int i;
    int q;
    cin>>q;
    for(i=1;i<=q;++i){
        int st,dest;
        cin>>st>>dest;
        if(nrd[st]<=BLOCKSIZE)
            cout<<solve(st,dest)<<'\n';
        else
            cout<<dist[st][dest]<<'\n';
    }
}

int main()
{
    read();
    create_forest();
    dfs_driver();
    dfs_init_driver();
    process_queries();
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 17 / 17
• Subtask 4: 23 / 23
• Subtask 5: 36 / 36
• Subtask 6: 10 / 10