제출 #1314773

#제출 시각아이디문제언어결과실행 시간메모리
1314773a5a7Valley (BOI19_valley)C++20
23 / 100
197 ms40896 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; const int MAXN = 100005; int up[MAXN][20]; int path[MAXN]; ll depth[MAXN]; int ed[MAXN]; bool shop[MAXN]; ll sh[MAXN]; ll dp[MAXN][20]; vector<vector<pair<int,pair<ll,int>>>> v; void dfs(int x, int prev){ up[x][0] = prev; for (auto nxt : v[x]){ if (nxt.first == prev) continue; path[nxt.first] = path[x] + 1; depth[nxt.first] = depth[x] + nxt.second.first; ed[nxt.second.second] = nxt.first; dfs(nxt.first, x); if (sh[nxt.first] != -1){ sh[x] = min(sh[x], sh[nxt.first]+nxt.second.first); } } dp[x][0] = sh[x] == 1e18 ? 1e18 : sh[x] - depth[x]; } int main(){ cin.tie(0); ios::sync_with_stdio(false); int n, s, q, e; cin >> n >> s >> q >> e; v.resize(n); fill(ed, ed+n, -1); for (int i = 1; i < n; i++){ int a, b; ll w; cin >> a >> b >> w; a--, b--; v[a].push_back({b, {w, i}}); v[b].push_back({a, {w, i}}); } fill(shop, shop+n, 0); fill(sh, sh+n, 1e18); for (int i = 0; i < s; i++){ int sho; cin >> sho; sho--; shop[sho] = 1; sh[sho] = 0; } e--; path[e] = 0; depth[e] = 0; dfs(e, -1); ll mini = 1e18; for (int i = 1; i < 20; i++){ for (int j = 0; j < n; j++){ up[j][i] = up[j][i-1] == -1 ? -1 : up[up[j][i-1]][i-1]; dp[j][i] = up[j][i-1] == -1 ? dp[j][i-1] : max(dp[j][i-1], dp[up[j][i-1]][i-1]); } } for (int i = 0; i < q; i++){ int a, b; cin >> a >> b; b--; a = ed[a]; ll prev = depth[b]; ll res = min(dp[a][0]+prev, sh[b]); if (path[a] > path[b]){ cout << "escaped\n"; continue; } for (int j = 0; j < 20; j++){ if ((1<<j)&(path[b]-path[a])){ res = min(res, dp[b][j] + prev); b = up[b][j]; } } if (b != a){ cout << "escaped\n"; }else if (res == mini){ cout << "oo\n"; }else{ cout << (res) << "\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...