Submission #675051

#	Time	Username	Problem	Language	Result	Execution time	Memory
675051		Trent	Valley (BOI19_valley)	C++17	100 / 100	457 ms	51376 KiB

valley

#include "bits/stdc++.h"
#include <cstring>
#include <fstream>

using namespace std;

#define ll long long
#define forR(i, x) for(int i = 0; i < x; ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define open(s) freopen(((string) s + ".in").c_str(), "r", stdin); freopen(((string) s + ".out").c_str(), "w", stdout)
#define all(i) i.begin(), i.end()
#define boost() cin.sync_with_stdio(0); cin.tie()
typedef pair<int, int> pii;

const int MN = 1e5 + 10, ME = 18;
const ll INF = MN * (1e9 + 10);
int anc[MN][ME], dep[MN];
ll dis[MN][ME], up[MN][ME];
bool shop[MN];
vector<pii> adj[MN];

void fill(int c, int p, int w, int d){
    anc[c][0] = p;
    up[c][0] = w;
    dep[c] = d;
    REP(e, 1, ME) {
        anc[c][e] = anc[c][e-1] == -1 ? -1 : anc[anc[c][e-1]][e-1];
        up[c][e] = anc[c][e-1] == -1 ? -1 : up[c][e-1] + up[anc[c][e-1]][e-1];
    }
    for(auto [i, w] : adj[c]) if(i != p) fill(i, c, w, d + 1);
}
int jmp(int c, int d){
    for(int e = ME - 1; e >= 0; --e) if((1 << e) <= d){
        c = anc[c][e];
        d -= (1 << e);
    }
    return c;
}
void dfs(int c, int p){
    dis[c][0] = shop[c] ? 0 : INF;
    for(auto [i, w] : adj[c]) if(i != p){
        dfs(i, c);
        dis[c][0] = min(dis[c][0], w + dis[i][0]);
    }
}

signed main() {
    int n, s, q, e; cin >> n >> s >> q >> e;
    vector<pii> edges;
    forR(g, n - 1){
        int a, b, w; cin >> a >> b >> w;
        edges.push_back({a, b});
        adj[a].push_back({b, w}); adj[b].push_back({a, w});
    }
    forR(g, s){
        int c; cin >> c;
        shop[c] = true;
    }
    fill(e, -1, 0, 0);
    dfs(e, -1);
    for(pii& i : edges) if(dep[i.first] > dep[i.second]) swap(i.first, i.second);
    REP(e, 1, ME) REP(i, 1, n + 1){
        dis[i][e] = anc[i][e] == -1 ? -1 : min(dis[i][e-1], up[i][e-1] + dis[anc[i][e-1]][e-1]);
    }
    forR(g, q){
        int i, r; cin >> i >> r;
        pii ed = edges[i - 1];
        if(dep[ed.second] <= dep[r] && ed.second == jmp(r, dep[r] - dep[ed.second]) && ed.first == anc[ed.second][0]){
            int amt = dep[r] - dep[ed.second] + 1;
            ll mi = INF;
            ll used = 0;
            int cur = r;
            for(int e = ME - 1; e >= 0; --e) if((1 << e) <= amt){
                mi = min(mi, used + dis[cur][e]);
                used += up[cur][e]; cur = anc[cur][e];
                amt -= (1 << e);
            }
            if(mi == INF) cout << "oo\n";
            else cout << mi << '\n';
        } else cout << "escaped\n";
    }
}

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