Submission #695792

#	Time	Username	Problem	Language	Result	Execution time	Memory
695792		Alish	Valley (BOI19_valley)	C++14	100 / 100	394 ms	102428 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);
#define int     long long

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 = 32, INF = 1e18 ;
ll D[N] , dist[N] , par[N][L] , mn[N][L], num[N];
int h[N] , st[N] , ft[N] , t=0;
vector<pll> E;
vector<pll> g[N] ;
int n , s, q, e;
int vis[N];
void dfs(int v, int p=0, int d=0, int H=0){

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

        D[v]=min(D[v], D[u]+w);
    }


    ft[v]=t;
    t++;
}


int32_t main(){

    fast_io
    cin>>n>>s>>q>>e;

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

    }
    memset(D, 63 , sizeof(D));
    for (int i=1; i<=n; i++)par[i][0]=i;
    for(int i=0; i<s; i++){

        int C; cin>>C;
        D[C]=0;
    }
    memset(mn , 63 , sizeof(mn));

    dfs(e, e) ;

    for(int i=0; i<n-1;  i++){
        if(h[E[i].F] < h[E[i].S]) swap(E[i].F , E[i].S);

    }

    for(int j=1; j<L; j++){
        for(int i=1; i<=n; i++){
            par[i][j]=par[par[i][j-1]][j-1];
        }
    }

    for(int i=1; i<=n; i++){
        num[i]=D[i]-dist[i];
    }

    for(int i=0; i<=n; i++){
        mn[i][0]=num[par[i][0]];
    }

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

    while(q--){
        ll ed, a; cin>>ed>>a;
        ed--;



        if(st[E[ed].F] <=st[a] && ft[E[ed].F]>=st[a]){
            ll b=E[ed].F;
            int ans=num[a];

            ll d= h[a]-h[b];
            ll c=a ;
            for(int i=L-1; i>=0; i--){
                if(d& ( 1<<i)){
                    ans= min(ans, mn[a][i]);
                    a=par[a][i];
                }
            }
            ans=min(ans, num[b]);
            //cout<<ans<<" "<<dist[c]<<endl;
            ans+=dist[c];


            if(ans<=INF) cout<<ans<<endl;

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



}

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