제출 #661231

#제출 시각아이디문제언어결과실행 시간메모리
661231jiahngValley (BOI19_valley)C++14
59 / 100
3050 ms28396 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll typedef pair<int,int> pi; typedef vector <int> vi; typedef vector <pi> vpi; typedef pair<pi, ll> pii; typedef set <ll> si; typedef long double ld; #define f first #define s second #define mp make_pair #define FOR(i,s,e) for(int i=s;i<=int(e);++i) #define DEC(i,s,e) for(int i=s;i>=int(e);--i) #define pb push_back #define all(x) (x).begin(), (x).end() #define lbd(x, y) lower_bound(all(x), y) #define ubd(x, y) upper_bound(all(x), y) #define aFOR(i,x) for (auto i: x) #define mem(x,i) memset(x,i,sizeof x) #define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define maxn 100010 #define INF (ll)1e18 #define MOD 1000000007 typedef pair <vi, int> pvi; typedef pair <int,pi> ipi; typedef vector <pii> vpii; int N,S,Q,E,I,R; int A[maxn], B[maxn], W[maxn], x; bool shop[maxn]; vpi adj[maxn]; int co = 0; int st[maxn], en[maxn], depth[maxn]; void dfs(int x, int p){ st[x] = co++; aFOR(i, adj[x]) if (i.f != p){ depth[i.f] = depth[x] + 1; dfs(i.f,x); } en[x] = co - 1; } vpi queries[maxn]; int ans[maxn]; vi C[maxn]; int dist[maxn]; int32_t main(){ cin >> N >> S >> Q >> E; FOR(i,1,N-1){ cin >> A[i] >> B[i] >> W[i]; adj[A[i]].pb(pi(B[i], W[i])); adj[B[i]].pb(pi(A[i], W[i])); } FOR(i,1,S){ cin >> x; shop[x] = 1; } dfs(E,-1); FOR(i,1,N-1){ if (depth[A[i]] > depth[B[i]]) swap(A[i], B[i]); // A is the parent } FOR(i,1,Q){ cin >> I >> R; if (!(st[B[I]] <= st[R] && st[R] <= en[B[I]])) ans[i] = -2; else{ queries[B[I]].pb(pi(R, i)); } } FOR(i,1,N) C[depth[i]].pb(i); priority_queue <pi, vector <pi>, greater <pi> > pq, pq2; mem(dist, -1); DEC(i,N-1,0){ while (!pq2.empty()){ pq.push(pq2.top()); pq2.pop(); } aFOR(j, C[i]){ if (shop[j]){ dist[j] = 0; pq.push(pi(0, j)); } } while (!pq.empty()){ pi cur = pq.top(); pq.pop(); if (cur.f != dist[cur.s]) continue; if (depth[cur.s] == i-1){ pq2.push(cur); continue; } aFOR(j, adj[cur.s]) if (dist[j.f] == -1 || dist[j.f] > cur.f + j.s){ dist[j.f] = cur.f + j.s; pq.push(pi(dist[j.f], j.f)); } } aFOR(j, C[i]){ aFOR(k, queries[j]){ ans[k.s] = dist[k.f]; } } } FOR(i,1,Q){ if (ans[i] == -2) cout << "escaped\n"; else if (ans[i] == -1) cout << "oo\n"; else cout << ans[i] << '\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...