Submission #1316430

#TimeUsernameProblemLanguageResultExecution timeMemory
1316430blue_phoenixxValley (BOI19_valley)C++20
100 / 100
236 ms46308 KiB
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdint>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <stack>
#include <string>
#include <set>
#include <thread>
#include <type_traits>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define fast()                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);
#define F(i, l, r) for (int i = l; i < l + r; i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define PI acos(-1)
#define bit_len(n) (n?(64 - __builtin_clzll(n)):0)
#define bit_count(n) __builtin_popcountll(n)
#define yes(i) cout << (i ? "Yes" : "No") << endl;
#define X first
#define Y second
#define sz(v) (int)(v).size()
#define vvl(x, n, m, val) vector<vector<ll>> x(n, vector<ll>(m, val))
#define bb __int128_t
typedef long long ll;
typedef std::pair<int, int> pi;
ll inf_ll = 1e18;
const ll inf = 1e8;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<pll> vp;
mt19937_64 mt(727);
uniform_int_distribution<ll> uni(1, inf / 2);
const int Mod[] = {998244353, (int)1e9 + 7};
const int mod = Mod[1];
const int max_n = 1e6 + 5;
const int N = 2e5+5;
vi dr = {-1, 1, 0, 0};
vi dc = {0, 0, -1, 1};
string dir = "DURL";
bool pow(bb a, int n, ll lim)
{
    bb m = 1;
    for (int i = 1; i <= n; i++) {
        m = m * a;
        if (m > lim) {
            return false;
        }
    }
    return true;
}
ll ncr(ll n, ll k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    k = min(k, n - k);
    ll res = 1;
    F(i, 0, k)
    {
        res = (ll)(res * (n - i));
        res = (ll)res / (i + 1);
    }
    return res;
}
int sqr(ll x)
{
    ll l = 0, r = x;
    int val = 0;
    while (l <= r)
    {
        ll m = (l + r) / 2;
        if (m * m >= x)
        {
            r = m - 1;
            val = m;
        }
        else
            l = m + 1;
    }
    return val;
}
void chmin(int &a, int b)
{
    a = min(a, b);
}
void chmax(int &a, int b)
{
    a = max(a, b);
}

// LCA by binary lifting O(NlogN) precomp and O(logN) per query

const int l = 20;
vi adj[N];
vi depth(N);
int timer = 0;
vi in(N), out(N);
int up[N][20];

void dfs(int u, int p) {
    timer++;
    in[u] = timer;
    up[u][0] = p;
    for (int j = 1; j < l; j++) {
        up[u][j] = up[up[u][j - 1]][j - 1];
    }
    for (auto v: adj[u]) {
        if (v != p) {
            depth[v] = 1 + depth[u];
            dfs(v, u);
        }
    }
    out[u] = ++timer;
}

//checks if a is an ancestor of b
bool is_anc(int a, int b) {
    return (in[a] <= in[b] && out[a] >= out[b]);
}

int lca(int u, int v) {
    if (is_anc(u, v)) {
        return u;
    }
    if (is_anc(v, u)) {
        return v;
    }
    for (int j = l - 1; j >= 0; j--) {
        if (!is_anc(up[u][j], v)) {
            u = up[u][j];
        }
    }
    return up[u][0];
}

void solve() {
    int n, s, q, e;
    cin >> n >> s >> q >> e;
    vector<array<int,4>>ed(n-1);
    for (int i = 0; i < n-1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        adj[u].pb(v);
        adj[v].pb(u);
        ed[i] = {u, v, w, i};
    }
    e--;
    for (int j = 0; j < l; j++) {
        up[e][j] = e;
    }
    dfs(e, e);
    vector<ll>wt(n);
    vector<int>ind(n-1);
    for (auto [u, v, w, i] : ed) {
        int put = u;
        if (depth[u] < depth[v]) {
            put = v;
        }
        wt[put] = w;
        ind[i] = put;
    }
    vector<ll>sum(n);
    vector<ll>path(n, inf_ll);
    vector<bool>shop(n);
    for (int i = 0; i < s; i++) {
        int x;
        cin >> x;
        x--;
        shop[x] = true;
    }
    function<void(int,int)>dfs1=[&](int u, int p) {
        if (shop[u]) {
            path[u] = sum[u];
        }
        for (int v : adj[u]) {
            if (v != p) {
                sum[v] = sum[u] + wt[v];
                dfs1(v, u);
                path[u] = min(path[u], path[v]);
            }
        }
    };
    dfs1(e, e);
    vector<vector<ll>>jump(n, vector<ll>(l, inf_ll));
    for (int i = 0; i < n; i++) {
        if (path[i]!=inf_ll) {
            path[i] -= 2*sum[i];
            for (int j = 0; j < l; j++) {
                jump[i][j] = path[i];
            }
        }
    }
    function<void(int,int)>build=[&](int u, int p) {
        jump[u][0] = min(path[p], path[u]);
        for (int j = 1; j < l; j++) {
            jump[u][j] = min(jump[u][j-1], jump[up[u][j-1]][j-1]);
        }
        for (int v : adj[u]) {
            if (v != p) {
                build(v, u);
            }
        }
    };
    build(e, e);
    while (q--) {
        int i, r;
        cin >> i >> r;
        i--;
        r--;
        int x = ind[i];
        if (lca(x, r)!=x) {
            cout << "escaped\n";
            continue;
        }
        int curr = r;
        ll ans = path[r];
        int dist = depth[r] - depth[x];
        for (int j = 0; j < l; j++) {
            if (dist&(1<<j)) {
                ans = min(ans, jump[curr][j]);
                curr = up[curr][j];
            }
        }
        if (ans == inf_ll) {
            cout << "oo\n";
        }
        else {
            cout << ans + sum[r] << "\n";
        }
    }
}

int main() {
    fast()
    /*freopen("cowland.in", "r", stdin);
    freopen("cowland.out", "w", stdout);*/
    cout << setprecision(10) << fixed;
    int tt = 1;
    auto begin = std::chrono::high_resolution_clock::now();
    while (tt--) {
        solve();
    }
    /*auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";*/
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...