Submission #1282362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282362		peanut	Valley (BOI19_valley)	C++20	59 / 100	97 ms	22768 KiB

valley

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 5;

struct edge {int u, v, w;};

int n, q, s, e;
vector<pair<int, int>> adj[maxn];
int dep[maxn], up[maxn][20], tin[maxn], tout[maxn], timer;
long long dist[maxn];
int shops[maxn];
edge edges[maxn];

void dfs(int u, int p)
{
    tin[u] = ++timer;
    for (auto [v, w] : adj[u])
    {
        if (v == p) continue;
        dep[v] = dep[u] + 1;
        dist[v] = dist[u] + w;
        up[v][0] = u;
        for (int i = 1; i < 20; ++i) up[v][i] = up[up[v][i-1]][i-1];
        dfs(v, u);
    }
    tout[u] = timer;
}

bool isancestor(int u, int v) {return tin[u] <= tin[v] && tout[v] <= tout[u];}

int lca(int u, int v)
{
    if (dep[u] < dep[v]) swap(u, v);
    int k = dep[u] - dep[v];
    for (int i = 0; i < 20; ++i) if (k >> i & 1) u = up[u][i];
    if (u == v) return u;
    for (int i = 19; i >= 0; --i)
    {
        if (up[u][i] != up[v][i])
        {
            u = up[u][i], v = up[v][i];
        }
    }
    return up[u][0];
}

long long calc(int u, int v) {return dist[u] + dist[v] - 2 * dist[lca(u, v)];}

namespace subtask123
{
    bool check() { return (n * q <= 1000000) || (s == n); }
    void solve()
    {
        while (q--)
        {
            int blocked, r; cin >> blocked >> r;
            int v = (dep[edges[blocked].u] < dep[edges[blocked].v]) ? edges[blocked].v : edges[blocked].u;
            if ((isancestor(v, r) ^ isancestor(v, e)) == 0)
            {
                cout << "escaped\n";
                continue;
            }
            if (s == n) cout << 0 << '\n';
            else
            {
                long long mindist = LLONG_MAX;
                for (int i = 1; i <= s; ++i)
                {
                    if ((isancestor(v, r) ^ isancestor(v, shops[i])) == 0) mindist = min(mindist, calc(shops[i], r));
                }
                if (mindist == LLONG_MAX) cout << "oo\n";
                else cout << mindist << '\n';
            }
        }
    }
}



int main()
{
    ios::sync_with_stdio(false); 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[i] = {u, v, w};
    }
    for (int i = 1; i <= s; ++i) cin >> shops[i];
    dfs(1, 0);
    if (subtask123::check()) subtask123::solve();
    return 0;
}

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