제출 #661232

#제출 시각아이디문제언어결과실행 시간메모리
661232jiahngValley (BOI19_valley)C++14
100 / 100
313 ms35328 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],sz[maxn]; int dp[maxn]; // min dist to go downwards from x to a shop void dfs(int x, int p){ st[x] = co++; sz[x] = 1; if (shop[x]) dp[x] = 0; else dp[x] = INF; aFOR(i, adj[x]) if (i.f != p){ depth[i.f] = depth[x] + i.s; dfs(i.f,x); sz[x] += sz[i.f]; dp[x] = min(dp[x], dp[i.f] + i.s); } en[x] = co - 1; } namespace UFDS{ int p[maxn]; int fl(int x){ if (p[x] == x) return x; return p[x] = fl(p[x]); } } vpi queries[maxn]; int ans[maxn]; int C[maxn]; int dist[maxn], D[maxn]; priority_queue <pi> pq[maxn]; void dfs2(int x,int p){ int mx = -1; aFOR(i, adj[x]) if (i.f != p){ dfs2(i.f, x); if (mx == -1 || pq[mx].size() < pq[i.f].size()) mx = i.f; } if (mx != -1) pq[mx].swap(pq[x]); pq[x].push(pi(C[x], x)); aFOR(i,adj[x]) if (i.f != p && i.f != mx){ while (!pq[i.f].empty()){ pq[x].push(pq[i.f].top()); pq[i.f].pop(); } } vi v; while (!pq[x].empty() && pq[x].top().f >= C[x]){ v.pb(pq[x].top().s); pq[x].pop(); } FOR(i,1,(int)v.size()-1){ int x = UFDS::fl(v[i]); UFDS::p[x] = UFDS::fl(v[0]); } if (!v.empty()){ D[UFDS::fl(v[0])] = C[x]; pq[x].push(pi(C[x], UFDS::fl(v[0]))); } aFOR(i, queries[x]){ ans[i.s] = D[UFDS::fl(i.f)] + depth[i.f]; } } 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[i] = dp[i] - depth[i]; // defn of C FOR(i,1,N) UFDS::p[i] = i; dfs2(E,-1); FOR(i,1,Q){ if (ans[i] == -2) cout << "escaped\n"; else if (ans[i] >= INF) 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...