Submission #1191726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191726		AlgorithmWarrior	Escape Route 2 (JOI24_escape2)	C++20	54 / 100	3093 ms	29968 KiB

Main

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

using namespace std;

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];

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 process_queries(){
    int i;
    int q;
    cin>>q;
    for(i=1;i<=q;++i){
        int st,dest;
        cin>>st>>dest;
        cout<<solve(st,dest)<<'\n';
    }
}

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

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