Submission #695651

#	Time	Username	Problem	Language	Result	Execution time	Memory
695651		Alish	Valley (BOI19_valley)	C++14	0 / 100	267 ms	53136 KiB

valley

#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef long double	ld;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp		        make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl
#define set_dec(x)	    cout << fixed << setprecision(x);
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);


ll mod = 1e9+7 ;

ll power(ll a, ll b)
{
    return (!b ? 1 : (b & 1 ? a * power(a * a % mod, b / 2) % mod : power(a * a % mod, b / 2) % mod));
}
const ll N = 2e5+23 , L = 23, INF = 1e18 ;
ll par[N][L] , mn[N][L];
ll dist[N] , distp[N];
ll h[N] , st[N], ft[N] , t;
vector<pll> E, g[N];
ll n , s , q, e;
ll  vis[N] ;

void dfs(int v, int p=0){
    st[v]=++t;
    for (auto pp: g[v]){
        int u = pp.F , w= pp.S;
        if(u!=p){
            par[u][0]=v;
            dist[u]= dist[v]+w;
            h[u]=h[v]+1;
            dfs(u,v);
        }
    }
    ft[v]=++t;
}

void DFS(int v, int p=0){
    if(vis[v])distp[v]=dist[v];

    else distp[v]=INF;

    for (auto pp: g[v]){
        int u = pp.F , w= pp.S;
        if(u!=p){
            DFS(u, v);
            distp[v]=min(distp[v] , distp[u]);
        }
    }

}
ll tof(ll v, ll h){
    if(!h) return distp[v];
    ll hh= __lg(h);
    return min(mn[v][h] , tof(par[v][hh] , h-(1<<hh) ));
}

int main()
{
    fast_io
    cin>>n>>s>>q>>e;
    for (int i=0; i<n-1; i++){
        ll u , v, w; cin>>v>>u>>w;
        g[v].pb({u,w});
        g[u].pb({v, w});
        E.pb({u, v});


    }
    for (int i=0; i<s; i++){
        int c; cin>>c;
        vis[c]=1;

    }
    dfs(e);
    DFS(e);
    for (int i=1; i<=n; i++){
            //cout<<distp[i]<<" ";
        distp[i]-=(2*dist[i]);
        //cout<<distp[i]<<":"<<i<<endl;
    }
    for (int i=1; i<=n; i++){

        if((1<<0)<=h[i]) mn[i][0]= min(distp[i] , distp[par[i][0]]);
    }
    for (int j=1; j<L; j++){
        for (int i=1; i<=n; i++){
            if( (1<<(j) <=h[i]) ){
                par[i][j]=par[par[i][j-1] ][j-1];
                mn[i][j]= min(mn[i][j-1] , mn[par[i][j-1]][j-1]);
            }
        }
    }

    while(q--){
        int l , b;
        cin>>l>>b;
        l--;
        int u= E[l].S , v= E[l].F;
        if(h[v]>h[u]) swap(u,v);

        if(st[u]<=st[b] && ft[u]>=ft[b]){
            ll d=h[b]-h[u];
            ll ans=tof(b, d)+dist[b];


            if(ans>1e14){
                    //cerr<<ans<<":";
                cout<<"oo"<<endl;
            }
            else cout<<ans<<endl;

        }
        else{
            cout<<"escaped"<<endl;
        }
    }



}

Compilation message (stderr)

valley.cpp: In function 'void DFS(int, int)':
valley.cpp:57:24: warning: unused variable 'w' [-Wunused-variable]
   57 |         int u = pp.F , w= pp.S;
      |                        ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 27
• Subtask 3: 0 / 23
• Subtask 4: 0 / 41