Submission #1315439

#TimeUsernameProblemLanguageResultExecution timeMemory
1315439hynmjValley (BOI19_valley)C++20
100 / 100
254 ms52004 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
const long long N = 2e5 + 5;
const long long lg = 20;
int a[N];
int start[N];
int en[N];
int weight[N];
int tim = 0;
int p[N];
int nearest[N];
vector<pair<int, int>> graph[N];
vector<pair<int, int>> edges;
int sp[N][lg];
int st[N][lg];
// const int N = 2e5 + 3;
int dist[N];
int mask;

void go_up(int &k, int binary)
{
    for (int i = 0; i < lg; i++)
    {
        mask = 1LL << i;
        if ((binary & mask) != 0)
        {
            k = sp[k][i];
        }
    }
}

int same_at_height(int u, int v)
{
    if (u == v)
        return v;
    for (int i = lg - 1; i >= 0; i--)
    {
        if (sp[u][i] != sp[v][i])
        {
            u = sp[u][i];
            v = sp[v][i];
        }
    }
    return sp[u][0];
}

int lca(int u, int v)
{
    if (dist[u] > dist[v])
        swap(u, v);
    // cout << u << ' ' << v << endl;
    // cout << dist[u] << ' ' << dist[v] << endl;
    int diff = dist[v] - dist[u];
    go_up(v, diff);
    // cout << u << ' ' << v << endl;
    if (u == v)
        return u;
    return same_at_height(u, v);
}
// Function to initialize the Sparse Table
void initialize(int n)
{
    // int n = ls.size();
    for (int i = 0; i <= n; i++)
    {
        sp[i][0] = p[i];
        st[i][0] = nearest[i] - weight[i];
    }
    for (int i = 1; i < lg; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            st[j][i] = min(st[j][i - 1], st[sp[j][i - 1]][i - 1]);
            sp[j][i] = sp[sp[j][i - 1]][i - 1];
        }
    }
}

int get(int l, int r)
{
    // l=st[l][0];
    int ans = 1e18;
    // get rth ancestor of l
    for (int i = lg - 1; i >= 0; i--)
    {
        if ((r >> i) & 1)
        {
            ans = min(ans, st[l][i]);
            l = sp[l][i];
        }
    }
    return ans;
}
void dfs(int node, int parent)
{
    // cout << "visited " << node << endl;
    p[node] = parent;
    start[node] = tim++;
    dist[node] = dist[parent] + 1;
    for (auto i : graph[node])
    {
        if (i.first == parent)
            continue;
        weight[i.first] = i.second + weight[node];
        dfs(i.first, node);
        // cout << node << " " << i.first << ' ' << nearest[i.first] << ' ' << i.second << endl;
        nearest[node] = min(nearest[node], nearest[i.first] + i.second);
    }

    en[node] = tim;
}
void solve()
{
    int n, s, q, E;
    int e;
    cin >> n >> s >> q >> E;
    int u, v, w;
    for (int i = 1; i < n; i++)
    {
        cin >> u >> v >> w;
        edges.push_back({u, v});
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
    fill(nearest, nearest + N, 1e15);
    for (int i = 0; i < s; i++)
    {
        // shops
        cin >> e;
        nearest[e] = 0;
    }

    dfs(E, 0);
    initialize(n + 1);
    // int q;
    // cin >> q;
    // for (int i = 0; i < n; i++)
    // {
    //     cout << st[i + 1][0] << ' ';
    // }
    // cout << endl;
    for (int i = 0; i < q; i++)
    {
        cin >> u >> v;
        u--;
        int tutau;

        // road u is cut
        if (start[edges[u].first] > start[edges[u].second])
            swap(edges[u].first, edges[u].second);
        tutau = edges[u].second;
        // cout << lca(3, 5) << endl;
        // cout << sp[5][0] << endl;
        if (lca(tutau, v) != tutau)
        {
            cout << "escaped\n";
            continue;
        }
        // cout << tutau << ' ' << edges[u].second << ' ' << v << endl;
        int up = dist[v] - dist[tutau];
        // cout << dist[v] << ' ' << dist[tutau] << endl;
        // /
        // cout << up << endl;

        // cout << p[5] << endl;
        // cout << st[5][1] << endl;
        int ans = get(v, up + 1) + weight[v];
        if (ans == 1e15)
        {
            cout << "oo" << endl;
        }
        else
        {
            cout << ans << endl;
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++)
    {
        // cout << "Case #" << i << ':' << ' ';
        solve();
        cout << endl;
    }
    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...