Submission #511169

#TimeUsernameProblemLanguageResultExecution timeMemory
511169akhan42Valley (BOI19_valley)C++17
0 / 100
139 ms20660 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> using namespace std; //using namespace __gnu_pbds; #define F first #define S second #define forn(i, n) for(int i = 0; i < n; ++i) #define forbn(i, b, n) for(int i = b; i < n; ++i) #define sz(v) (int)v.size() #define pb push_back #define eb emplace_back #define all(v) v.begin(), v.end() #define mp make_pair #define at(m, k) (m.find(k) != m.end() ? m[k] : 0) typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<ii> vii; typedef long long ll; //typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; template <class T> inline void mineq(T &a, T b) { a = min(a, b); } template <class T> inline void maxeq(T &a, T b) { a = max(a, b); } const int MX = 100 * 1000 + 10; ll INF = 1ll * 1000 * 1000 * 1000 * 1000 * 1000 * 100; struct Seg { int n; vector<ll> t; Seg(int n): n(n) { t.assign(2 * n, 0); } void update(int p, int val) { for(t[p += n] = val; p > 1; p >>= 1) t[p >> 1] = min(t[p], t[p ^ 1]); } ll query(int l, int r) { ll res = INF; for(l += n, r += n; l < r; l >>=1, r >>= 1) { if(l & 1) mineq(res, t[l++]); if(r & 1) mineq(res, t[--r]); } return res; } }; int n, s, q, e; vii gr[MX]; ii edge[MX]; int tin[MX], tout[MX]; bool magaz[MX]; int node2depth[MX]; int timer = -1; Seg mag2rast(MX); Seg rd(MX); vii v2q[MX]; ll ans[MX]; void dfs(int node = e, int par = 0, int depth = 0, ll dist = 0) { tin[node] = ++timer; mag2rast.update(timer, magaz[node] ? dist : INF); node2depth[node] = depth; for(ii nb_w: gr[node]) { int nb = nb_w.F, w = nb_w.S; if(nb == par) continue; dfs(nb, node, depth + 1, dist + w); } tout[node] = timer; } void dfs2(int node = e, int par = 0, int depth = 0, ll dist = 0) { ll rast_mag = mag2rast.query(tin[node], tout[node]); rd.update(depth, rast_mag - 2 * dist); if(sz(v2q[node])) { for(ii par1qi: v2q[node]) { int par = par1qi.F, qi = par1qi.S; int par_depth = node2depth[par]; ans[qi] = dist + rd.query(par_depth, depth); } } for(ii nb_w: gr[node]) { int nb = nb_w.F, w = nb_w.S; if(nb == par) continue; dfs2(nb, node, depth + 1, dist + w); } } bool par_son(int par, int son) { return tin[par] <= tin[son] && tout[son] <= tout[par]; } void solve() { cin >> n >> s >> q >> e; forbn(i, 1, n) { int a, b, w; cin >> a >> b >> w; edge[i] = mp(a, b); gr[a].eb(b, w); gr[b].eb(a, w); } forn(_, s) { int a; cin >> a; magaz[a] = true; } dfs(); forn(qi, q) { int i, r; cin >> i >> r; int a = edge[i].F, b = edge[i].S; if(!par_son(a, b)) swap(a, b); if(par_son(b, r)) { // cerr << b << ' ' << r << '\n'; v2q[r].eb(b, qi); } else { ans[qi] = -1; } } dfs2(); forn(qi, q) { if(ans[qi] == -1) { cout << "escaped\n"; } else if(ans[qi] > (INF / 10)) { cout << "oo\n"; } else { cout << ans[qi] << '\n'; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // freopen("262144.in", "r", stdin); // freopen("262144.out", "w", stdout); int t = 1; // cin >> t; while(t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...