//Never stop trying
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef string str;
typedef long long ll;
#define int ll
typedef double db;
typedef long double ld;
typedef pair<int,int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;
#define pb push_back
#define eb emplace_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"
const int MOD = 1e9+7; //998244353
const ll INF = 1e18;
const int nx[4]={0,0,1,-1}, ny[4]={1,-1,0,0}; //right left down up
void IO(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
const int MX=1e5+10;
int N,S,Q,E;
pi edges[MX];
vpi adj[MX];
bool shop[MX]={false};
int lvl[MX],tin[MX],tout[MX];
int timer;
int distE[MX],closest[MX],magic[MX];
int jump[MX][32],jumpMagic[MX][32];
void dfs(int u, int p, int l){
tin[u]=timer++;
lvl[u]=l;
for(auto v: adj[u]) if(v.fi!=p){distE[v.fi]=distE[u]+v.se; dfs(v.fi,u,l+1);}
tout[u]=timer++;
}
void dfs2(int u, int p){
for(auto v: adj[u]) if(v.fi!=p) dfs2(v.fi,u);
int ans=INF;
if(shop[u]) ans=distE[u];
for(auto v: adj[u]) if(v.fi!=p) ans=min(ans,closest[v.fi]);
closest[u]=ans;
}
void build(int u, int p){
jump[u][0]=p;
for(int i=1; i<32; i++) jump[u][i]=jump[jump[u][i-1]][i-1];
jumpMagic[u][0]=magic[u];
for(int i=1; i<32; i++) jumpMagic[u][i]=min(jumpMagic[u][i-1],jumpMagic[jump[u][i-1]][i-1]);
for(auto v: adj[u])if(v.fi!=p) build(v.fi,u);
}
bool ancestor(int u, int v){
if(tin[v]>=tin[u] && tout[v]<=tout[u]) return true;
else return false;
}
int32_t main(){
boost;
//IO();
cin>>N>>S>>Q>>E;
for(int i=0; i<N-1;i++){
int u,v,w; cin>>u>>v>>w;
edges[i]={u,v};
adj[u].pb({v,w});
adj[v].pb({u,w});
}
for(int i=0; i<S; i++){
int x; cin>>x; shop[x]=true;
}
timer=0; distE[E]=0;
dfs(E,E,1);
//for(int i=1; i<=N; i++) cout << distE[i] << ' '; cout << endl;
dfs2(E,E);
//for(int i=1; i<=N; i++) cout << closest[i] << ' '; cout << endl;
for(int u=1; u<=N; u++) magic[u]=-2*distE[u]+closest[u];
//for(int i=1; i<=N; i++) cout << magic[i] << ' '; cout << endl;
build(E,E);
while(Q--){
int idx,R; cin>>idx>>R; idx--;
int u=edges[idx].fi; if(lvl[edges[idx].se]>lvl[edges[idx].fi]) u=edges[idx].se;
if(!ancestor(u,R)) cout << "escaped" << endl;
else{
int ans=INF;
int d=distE[R];
for(int i=31; i>=0; i--) if(ancestor(u,jump[R][i])) ans=min(ans,jumpMagic[R][i]), R=jump[R][i];
ans=min(ans,magic[u]);
if(ans>=(1e15)) cout << "oo" << endl;
else cout << ans+d << endl;
}
}
return 0;
}
Compilation message
valley.cpp: In function 'void IO()':
valley.cpp:40:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("input.txt", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:41:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("output.txt", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2944 KB |
Output is correct |
2 |
Correct |
4 ms |
2944 KB |
Output is correct |
3 |
Correct |
4 ms |
3072 KB |
Output is correct |
4 |
Correct |
4 ms |
2944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2944 KB |
Output is correct |
2 |
Correct |
4 ms |
2944 KB |
Output is correct |
3 |
Correct |
4 ms |
3072 KB |
Output is correct |
4 |
Correct |
4 ms |
2944 KB |
Output is correct |
5 |
Correct |
4 ms |
3456 KB |
Output is correct |
6 |
Correct |
3 ms |
3456 KB |
Output is correct |
7 |
Correct |
3 ms |
3456 KB |
Output is correct |
8 |
Correct |
4 ms |
3456 KB |
Output is correct |
9 |
Correct |
4 ms |
3456 KB |
Output is correct |
10 |
Correct |
3 ms |
3456 KB |
Output is correct |
11 |
Correct |
3 ms |
3456 KB |
Output is correct |
12 |
Correct |
4 ms |
3456 KB |
Output is correct |
13 |
Correct |
3 ms |
3456 KB |
Output is correct |
14 |
Correct |
4 ms |
3456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
209 ms |
68856 KB |
Output is correct |
2 |
Correct |
221 ms |
68600 KB |
Output is correct |
3 |
Correct |
252 ms |
68984 KB |
Output is correct |
4 |
Correct |
280 ms |
69880 KB |
Output is correct |
5 |
Correct |
250 ms |
70136 KB |
Output is correct |
6 |
Correct |
432 ms |
71160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2944 KB |
Output is correct |
2 |
Correct |
4 ms |
2944 KB |
Output is correct |
3 |
Correct |
4 ms |
3072 KB |
Output is correct |
4 |
Correct |
4 ms |
2944 KB |
Output is correct |
5 |
Correct |
4 ms |
3456 KB |
Output is correct |
6 |
Correct |
3 ms |
3456 KB |
Output is correct |
7 |
Correct |
3 ms |
3456 KB |
Output is correct |
8 |
Correct |
4 ms |
3456 KB |
Output is correct |
9 |
Correct |
4 ms |
3456 KB |
Output is correct |
10 |
Correct |
3 ms |
3456 KB |
Output is correct |
11 |
Correct |
3 ms |
3456 KB |
Output is correct |
12 |
Correct |
4 ms |
3456 KB |
Output is correct |
13 |
Correct |
3 ms |
3456 KB |
Output is correct |
14 |
Correct |
4 ms |
3456 KB |
Output is correct |
15 |
Correct |
209 ms |
68856 KB |
Output is correct |
16 |
Correct |
221 ms |
68600 KB |
Output is correct |
17 |
Correct |
252 ms |
68984 KB |
Output is correct |
18 |
Correct |
280 ms |
69880 KB |
Output is correct |
19 |
Correct |
250 ms |
70136 KB |
Output is correct |
20 |
Correct |
432 ms |
71160 KB |
Output is correct |
21 |
Correct |
216 ms |
68296 KB |
Output is correct |
22 |
Correct |
235 ms |
67960 KB |
Output is correct |
23 |
Correct |
228 ms |
68216 KB |
Output is correct |
24 |
Correct |
363 ms |
69368 KB |
Output is correct |
25 |
Correct |
314 ms |
71320 KB |
Output is correct |
26 |
Correct |
281 ms |
68344 KB |
Output is correct |
27 |
Correct |
248 ms |
68092 KB |
Output is correct |
28 |
Correct |
261 ms |
68348 KB |
Output is correct |
29 |
Correct |
319 ms |
69240 KB |
Output is correct |
30 |
Correct |
310 ms |
70264 KB |
Output is correct |
31 |
Correct |
231 ms |
68472 KB |
Output is correct |
32 |
Correct |
224 ms |
68216 KB |
Output is correct |
33 |
Correct |
244 ms |
68472 KB |
Output is correct |
34 |
Correct |
299 ms |
69624 KB |
Output is correct |
35 |
Correct |
376 ms |
71416 KB |
Output is correct |
36 |
Correct |
262 ms |
69496 KB |
Output is correct |