제출 #954711

#제출 시각아이디문제언어결과실행 시간메모리
954711Angus_YeungValley (BOI19_valley)C++17
0 / 100
142 ms49912 KiB
#include <bits/stdc++.h> #define len first #define node second #define pii pair<ll, ll> typedef long long ll; const ll MOD = 1000000007LL; const ll INF = 1e15; using namespace std; struct edge { ll u, v, w, id; }; ll n, s, q, E, x, y, ans, tmp; bool c[100010]; ll t, up[20][100010], tin[100010], tout[100010], dep[100010]; ll dp[100010], val[20][100010]; edge e[100010]; vector<pii> a[100010]; void dfs(ll x, ll p, ll dis) { tin[x] = ++t; dp[x] = (c[x]? 0: INF); dep[x] = dis; up[0][x] = p; for (int i = 1; i <= 18; i++) up[i][x] = up[i-1][up[i-1][x]]; for (auto i: a[x]) { if (i.node == p) continue; dfs(i.node, x, dis+i.len); dp[x] = min(dp[x], dp[i.node]+i.len); } tout[x] = ++t; } void dfs2(ll x, ll p) { val[0][x] = dp[x]-dep[x]; for (int i = 1; i <= 18; i++) val[i][x] = min(val[i-1][x], val[i-1][up[i-1][x]]); for (auto i: a[x]) { if (i.node == p) continue; dfs2(i.node, x); } } bool isa(ll x, ll y) { return tin[x] <= tin[y] && tout[y] <= tout[x]; } int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin >> n >> s >> q >> E; for (int i = 1; i < n; i++) { cin >> e[i].u >> e[i].v >> e[i].w; a[e[i].u].push_back({e[i].w, e[i].v}); a[e[i].v].push_back({e[i].w, e[i].u}); e[i].id = i; } for (int i = 1; i <= n; i++) c[i] = 0; for (int i = 1; i <= s; i++) { cin >> x; c[x] = 1; } t = 0; dfs(E, E, 0); dfs2(E, E); // for (int i = 1; i <= n; i++) { // cout << i << ' ' << dep[i] << ' ' << dp[i] << "\n"; // for (int j = 0; j <= 5; j++) cout << val[j][i] << ' '; cout << "\n"; // } while (q--) { cin >> x >> y; if (isa(e[x].v, e[x].u)) swap(e[x].u, e[x].v); if (isa(e[x].v, y)) { if (dp[e[x].v] == INF) cout << "oo\n"; else if (e[x].v == y) cout << val[0][y] << "\n"; else { ans = INF; tmp = y; for (int i = 18; i >= 0; i--) { if (!isa(up[i][y], e[x].v)) { ans = min(ans, val[i][y]); y = up[i][y]; } } ans = min(ans, val[1][y]); cout << ans+dep[tmp] << "\n"; } } else cout << "escaped\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...