Submission #155140

#TimeUsernameProblemLanguageResultExecution timeMemory
155140GoldNextYearValley (BOI19_valley)C++14
23 / 100
989 ms50124 KiB
    #define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
    #include <bits/stdc++.h>
    using namespace std;
    #define sqr 340
    #define mid (l+r)/2
    #define pb push_back
    #define pob pop_back
    #define fi first
    #define se second
    #define lb lower_bound
    #define ub upper_bound
    #define ins insert
    #define era erase
    #define C continue
    #define mem(dp,i) memset(dp,i,sizeof(dp))
    #define mset multiset
    typedef long long ll;
    typedef long double ld;
    typedef pair<int,int> pi;
    typedef pair<ll,ll> pll;
    typedef vector<int> vi;
    typedef vector<ll> vll;
    typedef vector<pi> vpi;
    typedef vector<pll> vpll;
    const ll mod=1000000007;
    const ll inf=1e18*4;
    const ld pai=acos(-1);
    ll n,s,q,root;
    ll timer;
    vpll v[100009];
    pll e[100009];
    ll shop[100009];
    ll jumpnode[100009][20],jumpmagic[100009][20],magic[100009];
    ll depth[100009],st[100009],en[100009],w[100009];
    void dfs_calc(int node,int p,ll t){
            depth[node]=t;
            w[node]=w[p]+1;
            st[node]=timer++;
            for(auto u:v[node]){
                    if(u.fi!=p)dfs_calc(u.fi,node,t+u.se);
            }
            en[node]=timer-1;
    }
    void dfs_magic(int node,int p){
            for(auto u:v[node]){
                    if(u.fi!=p){
                            dfs_magic(u.fi,node);
                    }
            }
            if(shop[node])magic[node]=depth[node];
            else magic[node]=inf;
            for(auto u:v[node]){
                    if(u.fi!=p)magic[node]=min(magic[node],magic[u.fi]);
            }
    }
    void fill_magic(){
            for(int i=0;i<n;i++)magic[i]-=2*depth[i];
    }
    void dfs_lca(int node,int p){
            jumpnode[node][0]=p;
            jumpmagic[node][0]=magic[node];
            for(auto u:v[node]){
                    if(u.fi!=p)dfs_lca(u.fi,node);
            }
    }
    void fill_lca(){
            for(int j=1;j<20;j++){
                    for(int i=0;i<n;i++){
                            jumpnode[i][j]=jumpnode[jumpnode[i][j-1]][j-1];
                            jumpmagic[i][j]=min(jumpmagic[jumpnode[i][j-1]][j-1],jumpmagic[i][j-1]);
                    }
            }
    }
    int check(int a,int b,int x){
            if(w[a]<w[b])swap(a,b);
            return (st[a]<=st[x] && en[a]>=st[x]);
    }
    ll solve(int u,int p){
            ll mn=inf;
            for(int i=0;i<20;i++){
                    if(check(p,p,jumpnode[u][i])){
                            mn=min(mn,jumpmagic[u][i]);
                            u=jumpnode[u][i];
                    }
            }
            return min(mn,magic[p]);
    }
    int main(){
            cin>>n>>s>>q>>root;
            root--;
            for(int i=0;i<n-1;i++){
                    ll a,b,c;cin>>a>>b>>c,a--,b--;
                    e[i]={a,b};
                    v[a].pb({b,c});
                    v[b].pb({a,c});
            }
            for(int i=0;i<s;i++){
                    int x;cin>>x,x--;
                    shop[x]=1;
            }
            dfs_calc(root,root,0);
            dfs_magic(root,root),fill_magic();
            dfs_lca(root,root);fill_lca();
            while(q--){
                    int id,node;
                    cin>>id>>node,id--,node--;
                    int a=e[id].fi,b=e[id].se;
                    if(!check(a,b,node))cout<<"escaped"<<endl;
                    else{
                            int xxx=-1;
                            if(w[a]>w[b])xxx=a;
                            else xxx=b;
                            ll ans=depth[node]+solve(node,xxx);
                            if(ans>1e17)cout<<"oo"<<endl;
                            else cout<<ans<<endl;
                    }
            }
    }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...