Submission #899591

#	Time	Username	Problem	Language	Result	Execution time	Memory
899591		Mohammadamin__Sh	Valley (BOI19_valley)	C++17	100 / 100	195 ms	55228 KiB

valley

//In His Name
#include <bits/stdc++.h>
//#pragma GCC optimization("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")
using namespace std;
#define ll long long
#define int ll
typedef pair<int, int> pii;
#define F first
#define S second
#define pb push_back
#define bug(x) cout << "Ah shit , here we go again : " << x << endl
#define all(x) x.begin() , x.end()
const int maxn = 1e5 + 10, MOD = 1e9 + 7 , Lg = 22;
const ll INF = 1e18 + 100;

int n , s , q , root , par[maxn][Lg] , mini[maxn][Lg] , st[maxn] , fn[maxn] , t , val[maxn];
vector<pii> adj[maxn] , edge;
bool shop[maxn];

void Dfs(int v = root , int p = 0){
    par[v][1] = p , st[v] = ++t , par[v][0] = v;
    for(int i = 2 ; i < Lg ; i++) par[v][i] = par[par[v][i-1]][i-1] , mini[v][i] = INF;
    mini[v][0] = mini[v][1] = INF;
    for(pii u : adj[v]){
        if(u.S == p) continue;
        val[u.S] = val[v] + u.F;
        Dfs(u.S , v);
        mini[v][0] = min(mini[v][0] , mini[u.S][0] + u.F);
    }
    if(shop[v]) mini[v][0] = 0;
    fn[v] = t;
}

void BL(int p , int v){
    int res = mini[v][0] , x = v;
    for(int i = 19 ; i >= 1 ; i--){
        if(st[par[v][i]] >= st[p] and fn[p] >= fn[par[v][i]]) {
            res = min(res, mini[v][i]);
            v = par[v][i];
        }
    }
    if(res >= 1e15) cout << "oo\n";
    else cout << res + val[x] << '\n';
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0) , cout.tie(0);

    cin >> n >> s >> q >> root;
    edge.pb({0 , 0});
    for(int i = 1 ; i < n ; i++){
        int u , v , w;
        cin >> u >> v >> w;
        adj[v].pb({w , u});
        adj[u].pb({w , v});
        edge.pb({u , v});
    }
    for(int i = 1 ; i <= s ; i++){
        int x;
        cin >> x;
        shop[x] = true;
    }
    Dfs();
    for(int i = 1 ; i <= n ; i++) mini[i][0] -= val[i];
    for(int i = 1 ; i <= n ; i++) for(pii u : adj[i]) if(u.S != par[i][1]) mini[u.S][1] = min(mini[u.S][0] , mini[i][0]);
    for(int i = 2 ; i < Lg ; i++)
        for(int v = 1 ; v <= n ; v++)
            mini[v][i] = min(mini[v][i-1] , mini[par[v][i-1]][i-1]);
    while(q--){
        int x , y;
        cin >> x >> y;
        int u = edge[x].F , v = edge[x].S;
        if(st[u] > st[v]) swap(u , v);
        if(st[v] <= st[y] and fn[v] >= fn[y]) BL(v , y);
        else cout << "escaped\n";
    }

}

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