Submission #1271537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271537		hoangtien69	Valley (BOI19_valley)	C++20	100 / 100	120 ms	50568 KiB

valley

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int MAXN = 1e5 + 5;
const int LOG = 20;

int n, s, q, e;
vector<pii> adj[MAXN];
vector<pii> edges;
bool ck[MAXN];
int depth[MAXN];
int d[MAXN];
int up[MAXN][LOG];
int cost[MAXN];
int minn[MAXN][LOG];
int tin[MAXN];
int tout[MAXN];
int timer = 0;

void dfs(int u, int p)
{
    tin[u] = ++timer;
    depth[u] = depth[p] + 1;
    up[u][0] = p;
    for (int i = 1; i < LOG; i++)
    {
        up[u][i] = up[up[u][i-1]][i-1];
    }
    cost[u] = LLONG_MAX;
    if (ck[u])
    {
        cost[u] = d[u];
    }
    for (auto [v, w] : adj[u])
    {
        if (v == p) continue;
        d[v] = d[u] + w;
        dfs(v, u);
        cost[u] = min(cost[u], cost[v]);
    }
    minn[u][0] = cost[u] - 2 * d[u];
    tout[u] = timer;
}
int lift_min(int u, int k)
{
    int res = LLONG_MAX;
    for (int j = 0; j < LOG; j++)
    {
        if (k & (1 << j))
        {
            res = min(res, minn[u][j]);
            u = up[u][j];
        }
    }
    return res;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> s >> q >> e;
    for (int i = 1; i < n; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        edges.push_back({u, v});
    }
    for (int i = 1; i <= s; i++)
    {
        int u;
        cin >> u;
        ck[u] = true;
    }
    d[e] = 0;
    depth[0] = -1;
    dfs(e, 0);
    for (int j = 1; j < LOG; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            if (up[i][j-1] != 0)
            {
                minn[i][j] = min(minn[i][j-1], minn[up[i][j-1]][j-1]);
            }
            else
            {
                minn[i][j] = minn[i][j-1];
            }
        }
    }
    while (q--)
    {
        int qi, qr;
        cin >> qi >> qr;
        int u = edges[qi-1].first, v = edges[qi-1].second;
        if (depth[u] > depth[v]) swap(u, v);
        if (tin[v] <= tin[qr] && tout[qr] <= tout[v])
        {
            int k = depth[qr] - depth[v];
            int mn_val = lift_min(qr, k+1);
            if (mn_val > 1e15)
            {
                cout << "oo\n";
            }
            else
            {
                cout << mn_val + d[qr] << "\n";
            }
        }
        else
        {
            cout << "escaped\n";
        }
    }
}

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