Submission #1157751

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157751		MPG	Valley (BOI19_valley)	C++20	100 / 100	116 ms	58536 KiB

valley

// #pragma GCC optimization ("unroll-loops")
// #pragma GCC optimization ("O1, O2, O3, Ofast")
// #pragma GCC optimization ("trapv")
// #pragma GCC optimization ("sse, sse2, sse3, sse4, sse4.1, sse4.2, avx")



#include <bits/stdc++.h>
using namespace std;
typedef long long                           ll;
#define                                     max_heap priority_queue<ll>
#define                                     min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>> // size(), push(), top(), pop();
//#define                                     min_heap priority_queue<ll, vector<ll>, greater<ll>>
#define                                     sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define                                     filE freopen("in.txt", "r", stdin); freopen("out1.txt", "w", stdout);
#define                                     endl '\n'
#define                                     md(a) (a % mod + mod) % mod
//cout << setprecision(5) << f;
ll const maxn = 2e5 + 10;
ll const inf = 2e18;
ll const loG = 23;
ll const mod = 1e6 + 3;//998244353; //1e9 + 9, // 1e9 + 7;
ll const sq = 750;
ll power(ll a, ll b, ll mod){if (b == 0) return 1; if (b == 1) return a; ll x = power(a, b / 2, mod); return (((x * x) % mod) * (b % 2 ? a : 1)) % mod;}




ll n, t, q, root, dis[maxn], fas[maxn], fn[maxn], st[maxn], val[maxn], tim;
pair <ll, ll> par[loG][maxn];
pair <pair <ll, ll>, ll> yal[maxn];
vector <pair <ll, ll>> g[maxn];
bool sup[maxn];



void dfs(ll v, ll w, ll p){
    tim++;
    st[v] = tim;
    fas[v] = inf;
    if (sup[v])
        fas[v] = 0;
    if (p != -1){
        dis[v] = dis[p] + w;
        par[0][v].first = p;
    }
    for (auto u : g[v]){
        if (u.first != p){
            dfs(u.first, u.second, v);
            fas[v] = min(fas[v], u.second + fas[u.first]);
        }
    }
    tim++;
    fn[v] = tim;
}

bool ispar(ll v, ll u){
    if (st[v] <= st[u] && fn[v] >= fn[u])
        return 1;
    return 0;
}


ll ans(ll u, ll v){
    ll boz = inf;
    ll vv = v;
    for (int i = loG - 1; i >= 0; i--){
        if (!ispar(par[i][vv].first, u)){
            boz = min(boz, par[i][vv].second);
            vv = par[i][vv].first;
        }
    }
    if (vv != u)
        boz = min(boz, par[0][vv].second);
    return boz;
}




int main(){
sariE;// filE;

cin >> n >> t >> q >> root;
for (int i = 1; i < n; i++){
    ll a, b, c; cin >> a >> b >> c;
    yal[i].first.first = a;
    yal[i].first.second = b;
    yal[i].second = c;
    g[a].push_back({b, c});
    g[b].push_back({a, c});
}

for (int i = 1; i < t + 1; i++){
    ll x; cin >> x;
    sup[x] = 1;
}
dfs(root, 0, -1);
par[0][root] = {root, inf};
for (int i = 1; i < n + 1; i++){
    val[i] = fas[i] - dis[i];
    //cout << i << ' ' << fas[i] << ' ' << dis[i] << endl;
}
for (int i = 1; i < n; i++){
    if (st[yal[i].first.first] < st[yal[i].first.second])
        swap(yal[i].first.first, yal[i].first.second);
}

for (int i = 1; i < n + 1; i++){
    par[0][i].second = val[par[0][i].first];
}

for (int k = 1; k < loG; k++){
    for (int i = 1; i < n + 1; i++){
        par[k][i].first = par[k - 1][par[k - 1][i].first].first;
        par[k][i].second = min(par[k - 1][i].second, par[k - 1][par[k - 1][i].first].second);
    }
}

while (q--){
    ll l, v; cin >> l >> v;
    ll a = yal[l].first.first, b = yal[l].first.second;
    if (!ispar(a, v) || !ispar(b, v)){
        cout << "escaped" << endl;
        continue;
    }
    ll ret = val[v];
    ret = min(ret, ans(a, v));
    //cout << ret << endl;
    if (ret >= 1e18){
        cout << "oo" << endl;
    }
    else
        cout << dis[v] + ret << endl;

}






}

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