Submission #1223640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223640		onim	Valley (BOI19_valley)	C++20	100 / 100	149 ms	52108 KiB

valley

//         author : MOHAMMED OMAR FAIAZ ONIM
//         gmail : [e-mail]
//         戦え

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
const long long INF = 1e18;

long long bigmod(long long b, long long p, long long m){ // b ^ p % m
    if (p == 0)return 1;
    if (p % 2 == 0){
        long long x = bigmod(b, p / 2, m) % m;
        return (x * x) % m;
    }else return (b % m * bigmod(b, p - 1, m)) % m;
}
long long gcd(long long a, long long b){ return b == 0 ? a : gcd(b, a % b); } // assuming a>=b
long long lcm(long long a, long long b){ return (a / gcd(a, b)) * b * 1LL; }
long long inv(long long x) {
   if(x<=1)return x;
   return  mod - (mod / x) * inv(mod % x) % mod;
}
long long inv_mod(long long a, long long m) { return bigmod(a, m - 2, m); }// Using Fermat's theorem -> a^-1 ≡ a^(m-2) (mod m) where gcd(a,m)==1.
#define ll long long
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

void _print(long long t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(long double t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(unsigned long long t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.first); cerr << ","; _print(p.second); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

// ll dis[N];
// ll mn[N];
// bool shp[N];
// ll sz[N];
// ll fi[N];
// int timer;
// vector<vector<pair<ll,ll>>>adj(N);
// int tin[N];
// vector<ll>path;
// void dfs(int ver,int par,ll dist,int time){

//     mn[ver]=INF;
//     dis[ver]=dist;
//     fi[ver]=timer++;
//     tin[ver]=time;
//     path.push_back(ver);
//     sz[ver]=1;

//     if(shp[ver])mn[ver]=dist;

//     for(auto to : adj[ver]){
//         if(to.first!=par){
//             dfs(to.first,ver,dist+to.second,time+1);
//             mn[ver]=min(mn[ver],mn[to.first]);
//             sz[ver]+=sz[to.first];
//         }
//     }

// }

ll l;
vector<vector<pair<ll,ll>>> adj(N);

ll timer;
ll tin[N];
ll tout[N];
ll up[N][20];
ll sz[N];
ll mn[N];
bool shop[N];
ll mm[N][20];
ll dis[N];
ll n,s,q,e;
void dfs(int v, int p,ll dist)
{
    dis[v]=dist;
    tin[v]=++timer;
    up[v][0] = p;
    mn[v]=INF;

    if(shop[v])mn[v]=dist;

    for (auto u : adj[v]) {
        if (u.first != p){
            dfs(u.first, v,dist+u.second);
            mn[v]=min(mn[u.first],mn[v]);
        }
    }

    if(mn[v]!=INF){
        mm[v][0]=mn[v]-2*dis[v];
    }else mm[v][0]=INF;

    tout[v] = ++timer;
}

bool is_ancestor(ll u, ll v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
ll lca(ll u, ll v) {
  if (is_ancestor(u, v)) return u;
  if (is_ancestor(v, u)) return v;
  for (ll i = l; i >= 0; --i) {
    if (!is_ancestor(up[u][i], v))
      u = up[u][i];
  }
  return up[u][0];
}
void preprocess(ll root) {
    timer = 0;
    l = ceil(log2(n));
    dfs(root, root,0);
}

int main()
{
// #ifndef ONLINE_JUDGE
//         freopen("Error.txt", "w", stderr);
// #endif

    ios_base::sync_with_stdio(false);cin.tie(NULL);

    ll testcases=1;
    // cin>>testcases;

    while(testcases--){
        cin>>n>>s>>q>>e;
        

        ll a[n-1],b[n-1];


        for(ll  i=0;i<n-1;i++){
            ll u,v,w;
            cin>>u>>v>>w;

            a[i]=u;
            b[i]=v;

            adj[u].push_back({v,w});
            adj[v].push_back({u,w});
        }

        for(ll i=0;i<s;i++){
            ll x;
            cin>>x;
            shop[x]=1;
        }

        
        
        preprocess(e);

        for(int j=1;j<18;j++){
            for(int i=1;i<=n;i++){
                up[i][j]=up[up[i][j-1]][j-1];
                mm[i][j]=min(mm[up[i][j-1]][j-1],mm[i][j-1]);
            }
        }

        while(q--){
            ll l,r;
            cin>>l>>r;
            // cs++;

            --l;
            int u=a[l],v=b[l];

            if(is_ancestor(v,u))swap(u,v);
             
             if(!is_ancestor(v,r))cout<<"escaped\n";
             else{
                ll best=mm[v][0],extra=dis[r];
                for(int k=17;k>=0;k--){
                    if(is_ancestor(v,up[r][k])){
                        best=min(best,mm[r][k]);
                        r=up[r][k];
                    }
                }
                if(best==INF)cout<<"oo\n";
                else cout<<best+extra<<endl;
             }
        }
    }
}

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