Submission #695551

#TimeUsernameProblemLanguageResultExecution timeMemory
695551AlishValley (BOI19_valley)C++17
0 / 100
250 ms49212 KiB
#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 = 1e5+23 , L = 23, INF = 1e18 ;
ll par[N][L] , mn[N][L];
ll dist[N] , distp[N];
int h[N] , st[N], ft[N] , t;
vector<pll> E, g[N];
int n , s , q, e;
int 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]);
        }
    }

}


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({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++){
        mn[i][0]= min(distp[i] , distp[par[i][0]]);
    }
    for (int j=1; 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 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 pp=b;

            ll ans=INF;
            for (int i=L-1; i>=0; i--){
                if(d & (1<<i)){
                    ans= min(ans, mn[pp][i]);
                    pp=par[pp][i];
                }
            }
            ans+=dist[b];
            //if(h[b]-h[u]==0){
            //    ans=distp[b]+dist[b];
            //}
            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:57:24: warning: unused variable 'w' [-Wunused-variable]
   57 |         int u = pp.F , w= pp.S;
      |                        ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...