# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
201226 | 2020-02-09T23:27:01 Z | Lawliet | Valley (BOI19_valley) | C++17 | 305 ms | 50936 KB |
#include <bits/stdc++.h> using namespace std; typedef long long int lli; typedef pair<int,int> pii; const int LOG = 20; const int MAXN = 100010; const lli INF = 1000000000000000000LL; int n, s, q; int root; int curTime; int tin[MAXN]; int tout[MAXN]; lli prof[MAXN]; lli nextSub[MAXN]; lli dp[LOG][MAXN]; lli mn[LOG][MAXN]; bool isSpecial[MAXN]; pii edges[MAXN]; vector< int > adj[MAXN]; vector< int > peso[MAXN]; lli getValue(int cur) { if( nextSub[cur] == INF ) return INF; return nextSub[cur] - 2*prof[cur]; } void DFS(int cur, int p) { nextSub[cur] = INF; tin[cur] = ++curTime; if( isSpecial[cur] ) nextSub[cur] = prof[cur]; for(int k = 1 ; k < LOG ; k++) { int jump = dp[k - 1][cur]; dp[k][cur] = dp[k - 1][cur]; } for(int i = 0 ; i < adj[cur].size() ; i++) { int viz = adj[cur][i]; int w = peso[cur][i]; if( viz == p ) continue; dp[0][viz] = cur; prof[viz] = prof[cur] + w; DFS( viz , cur ); nextSub[cur] = min( nextSub[cur] , nextSub[viz] ); } mn[0][cur] = min( getValue( cur ) , getValue( p ) ); for(int k = 1 ; k < LOG ; k++) { int jump = dp[k - 1][cur]; mn[k][cur] = min( mn[k - 1][cur] , mn[k - 1][jump] ); } tout[cur] = ++curTime; } bool reachExit(int p, int cur) { bool inSubtree = ( tin[p] <= tin[cur] ); inSubtree = inSubtree && ( tout[cur] <= tout[p] ); return !inSubtree; } lli query(int p, int cur) { lli ans = INF; for(int k = LOG - 1 ; k >= 0 ; k--) { int jump = dp[k][cur]; if( jump != 0 && prof[jump] >= prof[p] ) { ans = min( ans , mn[k][cur] ); cur = dp[k][cur]; } } return ans; } int main() { scanf("%d %d %d %d",&n,&s,&q,&root); for(int k = 0 ; k < LOG ; k++) mn[k][0] = INF; for(int i = 1 ; i < n ; i++) { int U, V, W; scanf("%d %d %d",&U,&V,&W); adj[U].push_back( V ); adj[V].push_back( U ); peso[U].push_back( W ); peso[V].push_back( W ); edges[i] = { U , V }; } for(int i = 1 ; i <= s ; i++) { int shop; scanf("%d",&shop); isSpecial[ shop ] = true; } DFS( root , 0 ); for(int i = 1 ; i < n ; i++) { int U = edges[i].first; int V = edges[i].second; if( prof[U] > prof[V] ) swap( edges[i].first , edges[i].second ); } for(int i = 1 ; i <= q ; i++) { int ind, node; scanf("%d %d",&ind,&node); int p = edges[ind].second; if( reachExit( p , node ) ) { printf("escaped\n"); continue; } lli ans = query( p , node ); if( ans == INF ) printf("oo\n"); else printf("%lld\n",ans + prof[node]); } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 11 ms | 5496 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 11 ms | 5496 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 305 ms | 50936 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 11 ms | 5496 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |