Submission #695731

#	Time	Username	Problem	Language	Result	Execution time	Memory
695731		Alish	Valley (BOI19_valley)	C++14	23 / 100	337 ms	66940 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 = 32, INF = 1e18 ;
ll D[N] , dist[N] , par[N][L] , mn[N][L];
int h[N] , st[N] , ft[N] , t=0;
vector<pii> E;
vector<pii> g[N] ;
int n , s, q, e;
int vis[N];
void dfs(int v, int p=0){
    t++;
    st[v]=t;
    for (auto pp: g[v]){
        int u = pp.F , w= pp.S;
        if(u!=p){
            par[u][0]=v;
            h[u]= h[v]+1 ;
            dist[u]= dist[v]+w;
            dfs(u, v);

        }
    }
    t++;
    ft[v]=t;
}
void DFS(int v, int p=0){
    if(vis[v]){
        D[v]=dist[v];
    }
    else D[v]=INF;
    for (auto pp: g[v]){
        int u = pp.F , w= pp.S;
        if(u!=p){
            DFS(u, v);
            D[v]=min(D[v], D[u]);
        }
    }
}

int 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({v, u});

    }
    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++){
        D[i]-=(2*dist[i]);
        par[i][1]=par[i][0];
        par[i][0]=i;
        mn[i][0]=D[i];
        mn[i][1]= min(D[i] , D[par[i][1]]);
    }
    for (int j=2; j<L; j++){
        for (int i=1; i<=n; 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 v=E[l].F , u=E[l].S;
        int a=u;
        if(h[v]> h[u]){
            a=v;
        }


        if(st[a] <=st[b] && ft[a]>=ft[b]){
            ll d= h[a]-h[b];
            ll ans= D[b];
            //cout<<ans<<" ";
            int c=b;
            for (int i=L-2; i>=0; i--){
                if(d & ( 1<<i) ){
                ans= min ( ans, mn [b][i+1]);

                b= par[b][i+1];
                }
            }
            if(b!=a)ans= min ( ans, D[b]);
            ans+= dist[c];

            if( ans> 1e15){
                cout<<"oo"<<endl;
            }
            else cout<<ans<<endl;
        }
        else cout<<"escaped"<<endl;
    }


}

Compilation message (stderr)

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

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