Submission #1221539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221539		zyadhany	Valley (BOI19_valley)	C++20	100 / 100	181 ms	59456 KiB

valley

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
 
#define ll long long
#define ld long double
#define pl pair<ll, ll>
#define vi vector<ll>
#define vii vector<vi>
#define viii vector<vii>
#define vc vector<char>
#define vcc vector<vc>
#define vp vector<pl>
#define mi map<ll,ll>
#define mc map<char,int>
#define sortx(X) sort(X.begin(),X.end());
#define all(X) X.begin(),X.end()
#define allr(X) X.rbegin(),X.rend()
#define ln '\n'
#define YES {cout << "YES\n"; return;}
#define NO {cout << "NO\n"; return;}
#define MUN {cout << "-1\n"; return;}
using namespace std;
 
const int MODE = 1e9+7;

const int MXN = 1e5+10, lg = 18;
const ll INF = 1e16;
ll dp[MXN]{}, lvl[MXN]{};
ll val[MXN][lg], best[MXN][lg], par[MXN][lg];
vp adj[MXN];



void dfs(ll n, ll p, ll wp=0) {
    lvl[n] = lvl[p]+1;
    par[n][0] = p;
    val[n][0] = wp;
    best[n][0] = dp[p]+wp;
    for (int i = 1; i < lg; i++)
    {
        par[n][i] = par[par[n][i-1]][i-1];
        val[n][i] = val[n][i-1] + val[par[n][i-1]][i-1];
        best[n][i] = min(best[n][i-1], val[n][i-1] + best[par[n][i-1]][i-1]);
    }
    for (auto [neg, w] : adj[n]) if (neg != p) {
        dfs(neg, n, w);
    }
    for (auto [neg, w] : adj[n]) if (neg != p) {
        dp[n] = min(dp[n], dp[neg]+w);
    }
    for (int i = 0; i < lg; i++)
    {
        best[n][i] = min(best[n][i], dp[n]);
    }
}

ll kth(ll u, ll k) {
    for (int i = 0; i < lg; i++)
       if (k & (1<<i)) u = par[u][i];
    return u;    
}

ll lca(ll u, ll v) {
    if (lvl[u] < lvl[v]) swap(u, v);
    u = kth(u, lvl[u]-lvl[v]);
    if (u == v) return u;
    for (int i = lg - 1; i >= 0; i--)
        if (par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];        
    return par[u][0];
}

void solve(int tc) {
    ll n, m, q, ro;
    cin >> n >> m >> q >> ro;

    vp E(n);
    for (int i = 0; i < n-1; i++)
    {
        ll u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        E[i+1] = {u, v};
    }
    
    fill(dp, dp+MXN, INF);
    while (m--)
    {
        ll u; cin >> u;
        dp[u] = 0;
    }
    
    dfs(ro, 0);
    dfs(ro, 0);

    while (q--)
    {
        ll d, u;
        cin >> d >> u;

        auto [a, b] = E[d];
        if (lvl[a] < lvl[b]) swap(a, b);
        if (lca(a, u) != a || lca(b, u) != b) {
            cout << "escaped\n";
            continue;
        }

        ll res = dp[u];
        ll k = lvl[u] - lvl[a];
        ll add = 0;
        for (int i = 0; i < lg; i++)
        {
            if (k & (1<<i)) {
                res = min(res, best[u][i] + add);
                add += val[u][i];
                u = par[u][i];
            }
        }
        
        if (res == INF) cout << "oo\n";
        else cout << res << '\n';
    }
}

signed main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int size = 1;    
 
	// freopen("kangaroo.in", "r", stdin);
    // freopen("kangaroo.out", "w", stdout);
 
    // cin >> size;
    for (int i = 1; i <= size ; i++) solve(i);
    return 0;
}

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