Submission #444789

#	Time	Username	Problem	Language	Result	Execution time	Memory
444789		prvocislo	Valley (BOI19_valley)	C++17	100 / 100	209 ms	52540 KiB

valley

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxn = 1e5 + 5, logn = 17; const ll inf = 1e18;
struct edge { int v, i; ll w; };
vector<edge> g[maxn];
int p[logn][maxn]; ll sum[logn][maxn], mini[logn][maxn];
vector<ll> v(maxn, inf); vector<int> tin(maxn, -1), tout(maxn, -1), d(maxn, 0), ev(maxn);
int n, s, q, e, timer = 0;
bool in_subtree(int u, int v) { return tin[u] <= tin[v] && tout[v] <= tout[u]; } // je v v podstrome u?
void dfs(int u)
{
    tin[u] = timer++;
    for (const edge &i : g[u]) if (tin[i.v] == -1) 
    {
        d[i.v] = d[u]+1;
        dfs(i.v); ev[i.i] = i.v;
        p[0][i.v] = u, sum[0][i.v] = i.w;
        v[u] = min(v[u], v[i.v] + i.w);
    }
    tout[u] = timer-1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> s >> q >> e; e--;
    for (int i = 0; i < logn; i++) for (int j = 0; j < n; j++) p[i][j] = e, mini[i][j] = inf;
    for (int i = 0, a, b, w; i < n-1; i++)
    {
        cin >> a >> b >> w;
        g[--a].push_back({--b, i, w}), g[b].push_back({a, i, w});
    }
    for (int i = 0, x; i < s; i++) cin >> x, v[--x] = 0;
    dfs(e);
    for (int i = 0; i < n; i++) mini[0][i] = v[p[0][i]] + sum[0][i];
    for (int i = 1; i < logn; i++) for (int j = 0; j < n; j++)
    {
        p[i][j] = p[i-1][p[i-1][j]];
        sum[i][j] = sum[i-1][j] + sum[i-1][p[i-1][j]];
        mini[i][j] = min(mini[i-1][j], sum[i-1][j]+mini[i-1][p[i-1][j]]);
    }
    while (q--)
    {
        int i, vr; cin >> i >> vr; i--, vr--;
        int root = ev[i];
        if (!in_subtree(root, vr))
        {
            cout << "escaped\n";
            continue;
        }
        if (v[root] == inf)
        {
            cout << "oo\n";
            continue;
        }
        ll ans = v[vr], s = 0;
        for (int i = logn - 1; i >= 0; i--) if ((d[vr] - d[root]) & (1 << i))
        {
            ans = min(ans, s + mini[i][vr]);
            s += sum[i][vr], vr = p[i][vr];
        }
        cout << ans << "\n";
    }
    return 0;
}

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