Submission #766616

#	Time	Username	Problem	Language	Result	Execution time	Memory
766616		amogususus	Valley (BOI19_valley)	C++17	0 / 100	124 ms	45284 KiB

valley

#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx,avx2,bmi,popcnt")
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define prec fixed<<setprecision
#define endl '\n'
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define fout(name) freopen(name".out", "w", stdout);
using namespace std;
const int maxN=1e5+69;
const int mod =998244353;
ll n,k,q,h[maxN],d[maxN],dp[maxN],num[maxN],out[maxN],up[20][maxN],mn[20][maxN];
bitset<maxN> spec;
vector<pll> adj[maxN];
ll Time=0;
ll E;
void dfs(ll u,ll p=E){
    num[u]=++Time;
    for(auto[v,w]:adj[u])if(v!=p)d[v]=d[u]+w,h[v]=h[u]+1,dfs(v,u);
    dp[u]=1e18;
    if(spec[u])dp[u]=d[u];
    else for(auto[v,w]:adj[u])if(v!=p)dp[u]=min(dp[u],dp[v]);

    up[0][u]=p;
    if(dp[u]==1e18)mn[0][u]=1e18;
    else mn[0][u]=dp[u]-2*d[u];
    for(int i=1;i<20;i++)
        up[i][u]=up[i-1][up[i-1][u]],
        mn[i][u]=min(mn[i-1][u],mn[i-1][up[i-1][u]]);

    out[u]=Time;
}
bool is_ancestor(int u, int v) {return num[u] <= num[v] && out[v] <= out[u];}
void Enter(){
    cin>>n>>k>>q>>E;
    vector<pll> edg;edg.pb({0,0});
    ll u,v,w;
    for(int i=1;i<n;i++){
        cin>>u>>v>>w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
        edg.pb({u,v});
    }
    for(int i=1;i<=k;i++)cin>>u,spec[u]=1;
    dfs(E);
    for(auto&[u,v]:edg)if(h[u]<h[v])swap(u,v);
    while(q--){
        ll id;
        cin>>id>>u;
        v=edg[id].first;
        if(!is_ancestor(v,u))cout<<"escaped"<<endl;
        else {
            ll m=h[u]-h[v],r=1e18;
            for(int i=19;~i;i--)
                if(m>>i&1)r=min(r,mn[i][u]),u=up[i][u];
            r=min(r,mn[0][u]);
            if(r==1e18)cout<<"oo"<<endl;
            else cout<<r+d[u]+m+h[v]<<endl;
        }
    }
}
//amogus
signed main(){
    //open("GARDEN");
    cin.tie(nullptr);ios_base::sync_with_stdio(NULL);
    //ll t=1;cin>>t;while(t--)
    Enter();
}

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