제출 #667167

#제출 시각아이디문제언어결과실행 시간메모리
667167KahouValley (BOI19_valley)C++14
100 / 100
201 ms26052 KiB
#include<bits/stdc++.h> using namespace std; #define F first #define S second #define endl '\n' typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int N = 1e5 + 50; int n, s, q, r, h[N], st[N], ft[N], t; ll dis[N]; ll dp[N]; bool mark[N]; pii E[N]; vector<pii> adj[N]; vector<pii> vc[N]; ll out[N]; ll seg[N<<2]; void dfs(int u, int p) { st[u] = ++t; h[u] = h[p]+1; dp[u] = 1e18; if (mark[u]) dp[u] = 0; for (pii x:adj[u]) { int v = x.F, w = x.S; if (v == p) continue; dis[v] = dis[u] + w; dfs(v, u); dp[u] = min(dp[u], dp[v] + w); } ft[u] = t; } void build(int u, int tl, int tr) { if (tl == tr) { seg[u] = 1e18; return; } int md = (tl+tr)>>1; int lc = u<<1; int rc = u<<1|1; build(lc, tl, md), build(rc, md+1, tr); seg[u] = min(seg[lc], seg[rc]); } ll query(int u, int tl, int tr, int l, int r) { if (r < tl || tr < l) return 1e18; if (l <= tl && tr <= r) { return seg[u]; } int md = (tl+tr)>>1; int lc = u<<1; int rc = u<<1|1; return min(query(lc, tl, md, l, r), query(rc, md+1, tr, l, r)); } void upd(int u, int tl, int tr, int id, ll x) { if (tl == tr) { seg[u] = x; return; } int md = (tl+tr)>>1; int lc = u<<1; int rc = u<<1|1; if (id <= md) upd(lc, tl, md, id, x); else upd(rc, md+1, tr, id, x); seg[u] = min(seg[lc], seg[rc]); } void dfs2(int u, int p) { upd(1, 1, n, h[u], dp[u] - dis[u]); for (pii p:vc[u]) { int i = p.F, id= p.S; int v = (h[E[id].F] < h[E[id].S] ? E[id].S : E[id].F); if (!(st[v] <= st[u] && ft[v] >= ft[u])) { out[i] = -1; continue; } out[i] = query(1, 1, n, h[v], h[u]) + dis[u]; } for (pii x:adj[u]) { int v = x.F; if (v==p) continue; dfs2(v, u); } upd(1, 1, n, h[u], 1e18); } void solve() { cin >> n >> s >> q >> r; for (int i = 1; i <= n-1; i++) { int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); E[i] = {u, v}; } for (int i = 1; i <= s; i++) { int u; cin >> u; mark[u] = 1; } for (int i = 1; i <= q; i++) { int id, u; cin >> id >> u; vc[u].push_back({i, id}); } dfs(r,0); build(1,1,n); dfs2(r,0); for (int i = 1; i <= q; i++) { if (out[i] == -1) cout << "escaped" << endl; else if (out[i] >= 1e18) cout << "oo" << endl; else cout << out[i] << endl; } } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); solve(); 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...