Submission #1273548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273548		seraina	Fountain (eJOI20_fountain)	C++20	0 / 100	134 ms	56388 KiB

fountain

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

vector<ll>pre;
vector<ll>post;
vector<vector<ll>>g;
vector<vector<ll>>up;
vector<vector<ll>>cap;
vector<pair<ll,ll>>s;
vector<bool>vis;
ll timer=0;
ll current=0;

void dfs(ll v, ll p){
    vis[v]=true;
    pre[v]=timer++;
    up[v][0]=p;
    cap[v][0]=cap[p][0]+s[v+1].second;
    for(ll i=1; i<25; i++){
        up[v][i]=up[up[v][i-1]][i-1];
        cap[v][i]=cap[v][i-1]+cap[up[v][i-1]][i-1];
    }
    for(ll u:g[v]){
        if(u!=p){
            dfs(u,v);
        }
    }
    post[v]=timer++;
}

ll lca(ll v, ll c){
    for(ll i=24; i>=0; i--){
        if(cap[v][i]<=c){
            current=cap[v][i];
            v=up[v][i];
        }
    }
    return v;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll n,q;
    cin>>n>>q;
    pre.resize(n);
    post.resize(n);
    up.resize(n,vector<ll>(25,0));
    cap.resize(n,vector<ll>(25,0));
    g.resize(n);
    s.resize(n+1,{0,0});
    vis.resize(n,false);

    for(ll i=1; i<=n; i++){
        cin>>s[i].first>>s[i].second;
    }
    for(ll i=1; i<n+1; i++){
        for(ll j=i+1; j<n+1; j++){
            if(s[i].first<s[j].first){
                g[i-1].push_back(j-1);
                g[j-1].push_back(i-1);
                break;
            }
        }
    }
    for(ll i=0; i<n; i++){
        if(!vis[i] && g[i].size()>0) dfs(i,0);
    }
    for(ll i=0; i<q; i++){
        ll a,b;
        cin>>a>>b;
        ll res=lca(a-1,b);
        if(current<b){
            cout<<0<<'\n';
            continue;
        }
        cout<<res+1<<'\n';
    }
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40