제출 #424436

#제출 시각아이디문제언어결과실행 시간메모리
424436OdaveyValley (BOI19_valley)C++17
36 / 100
27 ms2508 KiB
// // ~oisín~ C++ Template // #include <bits/stdc++.h> #define MX_N 5001 #define mp make_pair #define mod7 1000000007 #define modpi 314159 #define PI 3.141592653589793238 #define pb push_back #define FastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define All(a) a.begin(),a.end() #define fi first #define se second #define ll long long int #define ull unsigned long long int int kx[8] = {+2, +2, -2, -2, +1, +1, -1, -1}; int ky[8] = {+1, -1, +1, -1, +2, -2, +2, -2}; int d9x[9] = {+1, +1, +1, +0, +0, +0, -1, -1, -1}; int d9y[9] = {+1, +0, -1, +1, +0, -1, +1, +0, -1}; int dx4[4] = {+0, +0, +1, -1}; int dy4[4] = {+1, -1, +0, +0}; ll gcd(ull a, ull b){ return (a==0)?b:gcd(b%a,a); } ll lcm(ull a, ull b){ return a*(b/gcd(a,b)); } const long long INF = 1e18; using namespace std; int _in[MX_N], _out[MX_N]; int glit = 0; ll mass[MX_N]; vector<pair<int, int> > adj[MX_N]; int p[MX_N]; int c[MX_N]; ll depth[MX_N]; ll minn[MX_N];//The cost of choosing this node as the "LCA". ie the second part of dist[u] + dist[v] - 2*dist[w] int jump[MX_N][48]; ll minn_jump[MX_N][48];//The minimum cost value in the step above at bool shoppe[MX_N]; void DFS(int at){ _in[at] = glit++; minn[at] = INF; for(auto& [to, id] : adj[at]){ if(p[at] == to){ continue; } c[id] = to; p[to] = at; depth[to] = mass[id] + depth[at]; DFS(to); minn[at] = min(minn[at], minn[to]); } if(shoppe[at]){ minn[at] = depth[at]; } _out[at] = glit++; return; } bool desc(int a, int b){ return(_in[a] >= _in[b] && _out[a] <= _out[b]); } int main(){ memset(shoppe, 0, sizeof(shoppe)); memset(jump, -1, sizeof(jump)); int n, s, Q, E; cin >> n >> s >> Q >> E; --E; p[E] = -1; depth[E] = 0ll; for(int i=0;i<n-1;++i){ int A, B; cin >> A >> B >> mass[i]; --A, --B; adj[A].pb({B, i}); adj[B].pb({A, i}); } for(int i=0;i<s;++i){ int at; cin >> at; --at; shoppe[at] = true; } DFS(E); for(int at=0;at<n;++at){ if(minn[at] != INF){ minn[at] -= 2ll*depth[at]; } jump[at][0] = p[at]; minn_jump[at][0] = minn[at]; } for(int k=1;k<48;++k){ for(int at=0;at<n;++at){ if(jump[at][k-1] == -1){ jump[at][k] = -1; minn_jump[at][k] = INF; }else{ jump[at][k] = jump[jump[at][k-1]][k-1]; minn_jump[at][k] = min(minn_jump[at][k-1], minn_jump[jump[at][k-1]][k-1]); } } } // cout << "minn:\n"; // for(int i=0;i<n;++i){ // cout << minn[i] << endl; // } // cout << "jump:\n"; // for(int i=0;i<n;++i){ // for(int k=0;k<4;++k){ // cout << jump[i][k] << ' '; // } // cout << endl; // } // cout << "minn_jump\n"; // for(int i=0;i<n;++i){ // for(int k=0;k<4;++k){ // cout << minn_jump[i][k] << ' '; // } // cout << endl; // } for(int q=0;q<Q;++q){ int r, v; cin >> r >> v; --r, --v; if(!desc(v, c[r])){ cout << "escaped\n"; continue; } int at = v; ll ans = min(minn[v], minn[c[r]]); for(int k=47;~k;--k){ if(jump[at][k] == -1){ continue; } if(!desc(jump[at][k], c[r])){ continue; } ans = min(ans, minn_jump[at][k]); at = jump[at][k]; } if(ans == INF){ cout << "oo\n"; }else{ cout << depth[v] + ans << endl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...