Submission #862990

#TimeUsernameProblemLanguageResultExecution timeMemory
862990Erfan1386YKitchen (BOI19_kitchen)C++17
0 / 100
1 ms5720 KiB
#include <bits/stdc++.h> #define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout); #define fast_io ios::sync_with_stdio(false);cin.tie(0); #define what(x) cerr << #x << " is " << x << endl; #define kill(x) {cout << x << '\n'; continue;} #define all(x) (x).begin(), (x).end() #define pii pair<int, int> #define pll pair<ll, ll> #define pb push_back #define ll long long #define F first #define S second const ll inf = 1e14, mod = 1e9 + 7, delta = 1e8, SQ = 800; //998244353 using namespace std; const ll N = 1e5 + 10, LG = 20; #define piii array<int, 3> int cnt, st[N], ft[N]; vector<piii> adj[N]; vector<int> maghaze, t; pll par[N], d[N], dd[N], edges[N]; bitset<N> mark; ll dis[N]; void dfs (int v, int p, int e) { t.pb(v); st[v] = cnt++; par[v] = pii(p, e); for (auto u: adj[v]) if (u[0] - p) dfs(u[0], v, u[2]); ft[v] = cnt; } void dfs (int v, int e) { mark[v] = true; for (auto u: adj[v]) if (u[2] != e && !mark[u[0]]) dfs(u[0], e); } bool cmp (piii a, piii b){ return a[1] < b[1]; } int32_t main() { fast_io; int n, s, q, e; cin >> n >> s >> q >> e; for (int i = 1; i < n; i++) { int u, v, w; cin >> u >> v >> w; adj[u].pb({v, w, i}); adj[v].pb({u, w, i}); edges[i] = pii(u, v); } for (int i = 1; i <= s; i++) { int v; cin >> v; maghaze.pb(v); } if (s == n) { dfs(1, -1, -1); for (int j = 1; j <= q; j++) { int ii, r; cin >> ii >> r; int u = edges[ii].F, v = edges[ii].S; if (v == par[u].F) swap(u, v); bool b = (st[e] >= st[v] && st[e] < ft[v]), bb = (st[r] >= st[v] && st[r] < ft[v]); if (b && bb) cout << "escaped\n"; else if (b || bb) cout << "0\n"; else cout << "escaped\n"; } } else { while (q--) { int ii, r; cin >> ii >> r; mark.reset(); dfs(r, ii); if (mark[e]) kill("escaped"); mark.reset(); priority_queue<pii, vector<pii>, greater<pii>> q; q.push(pii(0, r)); memset(dis, 63, sizeof dis); dis[r] = 0; while (q.size()) { int v = q.top().S; q.pop(); if (mark[v]) continue; mark[v] = true; for (auto u: adj[v]) { if (u[2] != ii && dis[u[0]] > dis[v] + u[1]) { dis[u[0]] = dis[v] + u[1]; q.push(pii(dis[u[0]], u[0])); } } } ll mn = inf; for (auto u: maghaze) mn = min(mn, dis[u]); if (mn == inf) cout << "oo\n"; else cout << mn << '\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...
#Verdict Execution timeMemoryGrader output
Fetching results...