Submission #1282426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282426		peanut	Valley (BOI19_valley)	C++20	100 / 100	101 ms	22588 KiB

valley

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
template<class X, class Y> bool maximize (X &x, const Y &y) {return x < y ? x = y, 1 : 0;}
template<class X, class Y> bool minimize (X &x, const Y &y) {return x > y ? x = y, 1 : 0;}
const int maxn = 1e5 + 5;
const int MOD = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct edge{int u, v, w;};
int n, s, q, e;
vector<pii> adj[maxn];
int depth[maxn], sz[maxn], heavy[maxn], head[maxn], par[maxn], timer, tin[maxn], tout[maxn], node[maxn];
ll dist[maxn], mindist[maxn], st[4*maxn];
bool shops[maxn];
edge edges[maxn];

void dfs(int u, int p)
{
    sz[u] = 1;
    par[u] = p;
    if (shops[u]) mindist[u] = 0;
    int bigchild = -1;
    for (auto [v, w] : adj[u])
    {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        dist[v] = dist[u] + w;
        dfs(v, u);
        mindist[u] = min(mindist[u], mindist[v] + w);
        sz[u] += sz[v];
        if (bigchild == -1 || sz[bigchild] < sz[v]) bigchild = v;
    }
    heavy[u] = bigchild;
}

void hld(int u, int p, int h)
{
    head[u] = h;
    tin[u] = ++timer;
    node[timer] = u;
    if (heavy[u] != -1) hld(heavy[u], u, h);
    for (auto [v, w] : adj[u])
    {
        if (v == p || v == heavy[u]) continue;
        hld(v, u, v);
    }
    tout[u] = timer;
}

void build(int id, int l, int r)
{
    if (l == r)
    {
        st[id] = mindist[node[l]] - ((mindist[node[l]] != INF) ? dist[node[l]] : 0);
        return ;
    }
    int mid = (l + r) >> 1;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    st[id] = min(st[id*2], st[id*2+1]);
}

ll query(int id, int l, int r, int u, int v)
{
    if (r < u || l > v) return INF;
    if (u <= l && r <= v) return st[id];
    int mid = (l + r) >> 1;
    return min(query(id*2, l, mid, u, v), query(id*2+1, mid+1, r, u, v));
}

ll getans(int u, int v)
{
    ll res = INF;
    while (head[u] != head[v])
    {
        if (depth[head[u]] < depth[head[v]]) swap(u, v);
        res = min(res, query(1, 1, n, tin[head[u]], tin[u]));
        u = par[head[u]];
    }
    if (depth[u] < depth[v]) swap(u, v);
    res = min(res, query(1, 1, n, tin[v], tin[u]));
    return res;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    memset(mindist, 0x3f, sizeof mindist);
    cin >> n >> s >> q >> e;
    for (int i = 1; i < n; ++i)
    {
        int u, v, w; cin >> u >> v >> w;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
        edges[i] = {u, v, w};
    }
    for (int i = 1; i <= s; ++i)
    {
        int x; cin >> x;
        shops[x] = 1;
    }
    dfs(e, 0);
    hld(e, 0, e);
    build(1, 1, n);
//    for (int i = 1; i <= n; ++i)
//    {
//        cout << tin[i] << ' ' << tout[i] << '\n';
//    }
    while (q--)
    {
        int b, r; cin >> b >> r;

        int v = (depth[edges[b].u] > depth[edges[b].v]) ? edges[b].u : edges[b].v;
        if (!(tin[v] <= tin[r] && tout[r] <= tout[v])) cout << "escaped\n";
        else
        {
            ll aaaaa = getans(r, v);
            //cout << aaaaa << '\n';
            if (aaaaa == INF) cout << "oo\n";
            else cout << aaaaa + dist[r] << '\n';
        }
    }
    return 0;
}

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