Submission #876582

#	Time	Username	Problem	Language	Result	Execution time	Memory
876582		imarn	Valley (BOI19_valley)	C++14	100 / 100	170 ms	50516 KiB

valley

#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
#define f first
#define s second
#define vi vector<int>
#define vll vector<long long>
#define vpii vector<pii>
using namespace std;
const int N=1e5+5;
vector<pii>g[N];
ll d[N]{0},pr[N][18],dp[N][19],dep[N]{0},node[N]{0};
pii ro[N];
int tin[N]{0},tout[N]{0};
int t=0;
ll dfs(int u,int p,int l){
    pr[u][0]=p;dep[u]=l;ll mn=1e17;
    for(int i=1;i<=17;i++)pr[u][i]=pr[pr[u][i-1]][i-1];
    if(node[u])mn=d[u];
    tin[u]=++t;
    for(auto v:g[u]){
        if(v.f==p)continue;
        d[v.f]=d[u]+v.s;
        mn=min(mn,dfs(v.f,u,l+1));
    }dp[u][0] = mn-2*d[u];tout[u]=t;
    return mn;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,s,q,e;cin>>n>>s>>q>>e;
    for(int i=1,u,v,w;i<=n-1;i++)cin>>u>>v>>w,g[u].pb({v,w}),g[v].pb({u,w}),ro[i]={u,v};
    for(int i=1,u;i<=s;i++)cin>>u,node[u]=1;
    dfs(e,e,0);
    for(int j=1;j<=18;j++)for(int i=1;i<=n;i++)dp[i][j]=min(dp[i][j-1],dp[pr[i][j-1]][j-1]);
    while(q--){
        int i,r,x,y;cin>>i>>r;tie(x,y)=ro[i];if(dep[x]<dep[y])swap(x,y);ll ans=1e17;int cur=r;
        if(!(tin[x]<=tin[r]&&tin[r]<=tout[x])){cout<<"escaped\n";continue;}
        for(int i=17;i>=0;i--)if(dep[x]<=dep[pr[cur][i]])ans=min(ans,dp[cur][i]+d[r]),cur=pr[cur][i];
        ans=min(ans,d[r]+dp[cur][0]);
        if(ans>=1e15)cout<<"oo\n";
        else cout<<ans<<"\n";
    }
}

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