Submission #1105074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105074		doducanh	Valley (BOI19_valley)	C++14	100 / 100	115 ms	60088 KiB

valley

///breaker
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
#define lc (id<<1)
#define rc ((id<<1)^1)
const int maxn=1e5+7;
const int inf=1e18+7;
vector<ii>adj[maxn];
bool dd[maxn];
int d1[maxn];
int d2[maxn];
int h[maxn];
int n,s,q,H;
int minn[25][maxn];
int cnt=0;
int in[maxn],out[maxn];
int p[25][maxn];
vector<ii>edges;
void dfs(int u,int par)
{
    if(dd[u])d1[u]=0;
    in[u]=++cnt;
    for(ii pp:adj[u]){
        int v=pp.fi,w=pp.se;
        if(v==par)continue;
        h[v]=h[u]+1;
        d2[v]=d2[u]+w;
        p[0][v]=u;
        dfs(v,u);
        d1[u]=min(d1[u],d1[v]+w);
    }
    out[u]=++cnt;
}
bool check(int u,int v)
{
    return (in[u]<=in[v]&&out[v]<=out[u]);
}
void sol(void){
    cin>>n>>s>>q>>H;
    for(int i=0;i<=n;i++){
        d1[i]=inf;
        d2[i]=0;
    }
    edges.push_back({0,0});
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
        edges.push_back({u,v});
    }
    for(int i=1;i<=s;i++){
        int u;
        cin>>u;
        dd[u]=1;
    }
    dfs(H,0);
    for(int i=1;i<=n;i++){
        minn[0][i]=-d2[p[0][i]]+d1[p[0][i]];
    }
    for(int i=1;i<=20;i++){
        for(int j=1;j<=n;j++){
            minn[i][j]=min(minn[i-1][j],minn[i-1][p[i-1][j]]);
            p[i][j]=p[i-1][p[i-1][j]];
        }
    }
    while(q--){
        int id,r;
        cin>>id>>r;
        int u=edges[id].fi,v=edges[id].se;
        if(h[u]<h[v])swap(u,v);
        if(!(check(u,r)&&check(v,r))){
            cout<<"escaped"<<"\n";
            continue;
        }
        int ans=-d2[r]+d1[r];
        int del=h[r]-h[u];
        int pre=r;
        for(int i=20;i>=0;i--)if(bit(del,i)){
            ans=min(ans,minn[i][r]);
            r=p[i][r];
        }
        if(ans+d2[pre]>=inf){
            cout<<"oo"<<"\n";
            continue;
        }
        cout<<ans+d2[pre]<<"\n";
    }
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        sol();
    }
    // you should actually read the stuff at the bottom
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

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