제출 #1097331

#제출 시각아이디문제언어결과실행 시간메모리
1097331PhuocValley (BOI19_valley)C++14
23 / 100
145 ms40392 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define BIT(mask, i) (((mask) >> (i)) & 1) #define MASK(i) (1LL << (i)) #define el '\n' template <class T1, class T2> bool maximize(T1 &a, T2 b) { if(a < b) {a = b; return true;} return false; } template <class T1, class T2> bool minimize(T1 &a, T2 b) { if(a > b) {a = b; return true;} return false; } const ll MOD = (ll)1e9 + 7; const int oo = (int)1e9 + 10; const ll INF = (ll)1e18 + 9LL; template <class T1, class T2> void add (T1 &a, T2 b) { a += b; if(a >= MOD) a -= MOD; } const int N = 100100; const int LOG = 18; int nVillage, nFarm, styn, nQuery; vector <pair<int, ll> > adj [N]; bool isFarm[N]; pair <int, int> queries [N]; struct edge { int u, v; ll c; edge (int _u = 0, int _v = 0, ll _c = 0) { u = _u; v = _v; c = _c; } } edges[N]; void init (void) { cin >> nVillage >> nFarm >> nQuery >> styn; for (int i = 1; i < nVillage; i++) { int u, v; ll c; cin >> u >> v >> c; adj[u].push_back(make_pair(v, c)); adj[v].push_back(make_pair(u, c)); edges[i] = edge (u, v, c); } for (int i = 1; i <= nFarm; i++) { int x; cin >> x; isFarm[x] = true; } } int fin[N], fout[N], dep[N], par[N][LOG]; ll dist[N], dp[N], minVal[N][LOG], val[N]; bool have_farm_in[N]; int tgDfs = 0; void dfs (int u, int p) { fin[u] = ++tgDfs; have_farm_in[u] = isFarm[u]; for (auto x : adj[u]) { int v = x.fi; if(v == p) continue; dep[v] = dep[u] + 1; dist[v] = dist[u] + x.se; par[v][0] = u; dfs (v, u); if(have_farm_in[v]) have_farm_in[u] = true; } fout[u] = tgDfs; } void calc (int u, int p) { dp[u] = isFarm[u] ? 0 : oo; for (auto x : adj[u]) { int v = x.fi; if(v == p) continue; calc(v, u); minimize(dp[u], dp[v] + x.se); } } void build_val (int u, int p) { if(p == 0) minVal[u][0] = dp[u] - dist[u]; else minVal[u][0] = min(dp[u] - dist[u], dp[p] - dist[p]); for (int i = 1; i < LOG; i++) { minVal[u][i] = min(minVal[u][i - 1], minVal[par[u][i - 1]][i - 1]); } for (auto x : adj[u]) { int v = x.fi; if(v == p) continue; build_val(v, u); } } int getMin (int u, int diff) { int ans = oo; for (int i = 0; i < LOG; i++) { if(BIT(diff, i)) { minimize(ans, minVal[u][i]); u = par[u][i]; } } return ans; } void solve (void) { dfs (styn, 0); calc (styn, 0); for (int j = 1; j < LOG; j++) for(int i = 1; i <= nVillage; i++) par[i][j] = par[par[i][j - 1]][j - 1]; memset(minVal, oo, sizeof minVal); // memset(dp, oo, sizeof dp); build_val(styn, 0); for (int lmao = 1; lmao <= nQuery; lmao++) { int ban, node; cin >> ban >> node; edge e = edges[ban]; int u = e.u, v = e.v; if(dep[v] < dep[u]) swap(u, v); if(!(fin[node] >= fin[v] && fin[node] <= fout[v])) { cout << "escaped" << el; } else { if(!have_farm_in[v]) { cout << "oo" << el; continue; } ll ans = INF; if(have_farm_in[node]) minimize(ans, dp[node]); int diff = dep[node] - dep[v]; minimize(ans, getMin(node, diff) + dist[node]); cout << ans << el; } } } int main (void) { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int ntest = 1; while (ntest--) { init(); 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...