Submission #1369070

#TimeUsernameProblemLanguageResultExecution timeMemory
1369070sameerValley (BOI19_valley)C++20
0 / 100
80 ms22788 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
const int sn = 1e5+7;
int i, j, di, n, s, q, e, t1, t2, ww, va, le[sn], ri[sn], dis[sn], cur, pap[18][sn]; bool sh[sn]; 
ll mid[sn], qee[sn];
array<int, 3> tem;
array<int, 2> tem2;
vector<array<int, 3>> v[sn];
vector<array<int, 2>> qe[sn];

void dfs(int cu, int pa){
 for(array<int, 3> z: v[cu]){
 if(z[0] != pa){
 dfs(z[0], cu); 
 mid[cu] = min(mid[cu], mid[z[0]]+z[1]);
 // cout << z[0] << ' '; 
 }
 }  // cout << '\n';
//  cout << cu << ' ' << mid[cu] << '\n';
}

void dfs2(int cu, int pa){
 dis[cu] = di; mid[cu] -= di;
 // cout << cu << ' ' << dis[cu] << ' ' << mid[cu] << '\n';
 for(array<int, 3> z: v[cu]){
 if(z[0] != pa){
 di += z[1];
 dfs2(z[0], cu);
 di -= z[1]; 
 }
 }
}

void dfs3(int cu, int pa){
 for(array<int, 3> z: v[cu]){
 if(z[0] == pa) continue;
 cur = cu;
 for( j = 17; j >= 0; j--) if(mid[pap[j][cur]] >= mid[z[0]]) cur = pap[j][cur];
 if(mid[cu] < mid[z[0]]) pap[0][z[0]] = cu;
 else pap[0][z[0]] = pap[0][cur];
 for( j = 1; j < 18; j++) pap[j][z[0]] = pap[j-1][pap[j-1][z[0]]];
 dfs3(z[0], cu);
 }
}

void dfs4(int cu, int pa){

 for(array<int, 2> z: qe[cu]){
 // cout << cu << ' ' << z[0] << ' ' << z[1] << '\n';
 if(!sh[z[0]]) qee[z[1]] = -1;
 else{
 di = max(dis[le[z[0]]], dis[ri[z[0]]]);
 // cout << le[z[0]] << ' ' << ri[z[0]] << ' ' << di << ' ';
 cur = cu;
 for( j = 17; j >= 0; j--) if(dis[pap[j][cur]] >= di) cur = pap[j][cur];
 // cout << cur << '\n';
 qee[z[1]] = mid[cur]+dis[cu];
 }
 }

 for(array<int, 3> z: v[cu]){
 if(z[0] == pa) continue;
 sh[z[2]] = 1;
 dfs4(z[0], cu);
 sh[z[2]] = 0;
 }

}

void run(){
}

int main(){
 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 // int tt; cin >> tt; while(tt--) run();
 cin >> n >> s >> q >> e;
 
 for( i = 1; i < n; i++){ 
 cin >> t1 >> t2 >> ww; 
 le[i] = t1; ri[i] = t2;
 tem[0] = t2;
 tem[1] = ww;
 tem[2] = i;
 v[t1].push_back(tem);
 tem[0] = t1;
 v[t2].push_back(tem);
 sh[i] = 0;
 }
 
 for( i = 1; i <= n; i++) mid[i] = 1e18;
 for( i = 1; i <= s; i++) cin >> va, mid[va] = 0;
 
 mid[e] = -1e18; 
 dfs(e, -1);
 
 di = 0;
 dfs2(e, -1);
 
 for( i = 0; i < 18; i++) pap[i][e] = e;
 dfs3(e, -1);

 for( i = 0; i < q; i++){
 cin >> t1 >> t2;
 tem2[0] = t1; tem2[1] = i;
 qe[t2].push_back(tem2);
 }
 
 dfs4(e, -1);

 for( i = 0; i < q; i++){
 if(qee[i] == -1) cout << "escaped\n";
 else if(qee[i] >= 1e18) cout << "oo\n";
 else cout << qee[i] << '\n';
 }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...