#include<bits/stdc++.h>
#define maxn 100005
#define inf 1000000000000000000ll
#define pinf 10000000000000000ll
using namespace std;
int n,s,q,e;
vector<pair<int,int> > neigh[maxn];
long long d[maxn];
int ch[maxn];
long long md[maxn];
long long dd[maxn];
bool ex[maxn];
void dfs(int u,int pred=0) {
if(ex[u]) md[u]=d[u];
else md[u]=inf;
for(auto eg:neigh[u]) {
int v=eg.first;
if(v!=pred) {
d[v]=d[u]+eg.second;
ch[v]=ch[u]+1;
dfs(v,u);
//cout<<u<<" "<<v<<" "<<" "<<eg.second<<endl;
md[u]=min(md[u],md[v]);
}
}
dd[u]=md[u]-2*d[u];
//cout<<u<<" "<<md[u]<<" "<<dd[u]<<endl;
}
long long seg[4*maxn];
void add(int id,int l,int r,int p,long long v) {
if(l==r) {
seg[id]=v;
return;
}
int m=(l+r)/2;
if(p<=m) add(id*2+1,l,m,p,v);
else add(id*2+2,m+1,r,p,v);
seg[id]=min(seg[id*2+1],seg[id*2+2]);
}
long long query(int id,int l,int r,int x,int y) {
if(y<l || r<x) return inf;
if(x<=l && r<=y) return seg[id];
int m=(l+r)/2;
long long v1=query(id*2+1,l,m,x,y);
long long v2=query(id*2+2,m+1,r,x,y);
return min(v1,v2);
}
int ux[maxn];
int vx[maxn];
long long ans[maxn];
vector<pair<int,int> > queries[maxn];
bool ins[maxn];
void dfs_ans(int u,int pred=0) {
ins[u]=true;
add(0,0,n-1,ch[u],dd[u]);
for(auto que:queries[u]) {
int road=que.first;
int id=que.second;
if(!ins[ux[road]] || !ins[vx[road]]) {
ans[id]=-1;
}
else {
int anc=ux[road];
if(d[vx[road]]>d[ux[road]]) anc=vx[road];
ans[id]=d[u]+query(0,0,n-1,ch[anc],ch[u]);
}
}
for(auto eg:neigh[u]) {
int v=eg.first;
int w=eg.second;
if(v!=pred) {
dfs_ans(v,u);
}
}
ins[u]=false;
}
int main() {
scanf("%d %d %d %d",&n,&s,&q,&e);
for(int i=1;i<=n-1;i++) {
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
ux[i]=u;
vx[i]=v;
neigh[u].push_back({v,w});
neigh[v].push_back({u,w});
}
for(int i=1;i<=s;i++) {
int p;
scanf("%d",&p);
ex[p]=true;
}
dfs(e);
for(int i=1;i<=q;i++) {
int r,v;
scanf("%d %d",&r,&v);
queries[v].push_back({r,i});
}
dfs_ans(e);
for(int i=1;i<=q;i++) {
if(ans[i]==-1) printf("escaped\n");
else {
if(ans[i]<pinf) printf("%lld\n",ans[i]);
else printf("oo\n");
}
}
return 0;
}
Compilation message
valley.cpp: In function 'void dfs_ans(int, int)':
valley.cpp:70:13: warning: unused variable 'w' [-Wunused-variable]
70 | int w=eg.second;
| ^
valley.cpp: In function 'int main()':
valley.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%d %d %d %d",&n,&s,&q,&e);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | scanf("%d %d %d",&u,&v,&w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
valley.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
90 | scanf("%d",&p);
| ~~~~~^~~~~~~~~
valley.cpp:96:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | scanf("%d %d",&r,&v);
| ~~~~~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
5332 KB |
Output is correct |
2 |
Correct |
6 ms |
5332 KB |
Output is correct |
3 |
Correct |
5 ms |
5332 KB |
Output is correct |
4 |
Correct |
7 ms |
5332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
5332 KB |
Output is correct |
2 |
Correct |
6 ms |
5332 KB |
Output is correct |
3 |
Correct |
5 ms |
5332 KB |
Output is correct |
4 |
Correct |
7 ms |
5332 KB |
Output is correct |
5 |
Correct |
4 ms |
5204 KB |
Output is correct |
6 |
Correct |
4 ms |
5076 KB |
Output is correct |
7 |
Correct |
3 ms |
5204 KB |
Output is correct |
8 |
Correct |
4 ms |
5092 KB |
Output is correct |
9 |
Correct |
3 ms |
5076 KB |
Output is correct |
10 |
Correct |
3 ms |
5204 KB |
Output is correct |
11 |
Correct |
4 ms |
5204 KB |
Output is correct |
12 |
Correct |
4 ms |
5076 KB |
Output is correct |
13 |
Correct |
4 ms |
5160 KB |
Output is correct |
14 |
Correct |
4 ms |
5204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
160 ms |
19988 KB |
Output is correct |
2 |
Correct |
176 ms |
19584 KB |
Output is correct |
3 |
Correct |
158 ms |
19568 KB |
Output is correct |
4 |
Correct |
178 ms |
22220 KB |
Output is correct |
5 |
Correct |
154 ms |
21508 KB |
Output is correct |
6 |
Correct |
175 ms |
24524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
5332 KB |
Output is correct |
2 |
Correct |
6 ms |
5332 KB |
Output is correct |
3 |
Correct |
5 ms |
5332 KB |
Output is correct |
4 |
Correct |
7 ms |
5332 KB |
Output is correct |
5 |
Correct |
4 ms |
5204 KB |
Output is correct |
6 |
Correct |
4 ms |
5076 KB |
Output is correct |
7 |
Correct |
3 ms |
5204 KB |
Output is correct |
8 |
Correct |
4 ms |
5092 KB |
Output is correct |
9 |
Correct |
3 ms |
5076 KB |
Output is correct |
10 |
Correct |
3 ms |
5204 KB |
Output is correct |
11 |
Correct |
4 ms |
5204 KB |
Output is correct |
12 |
Correct |
4 ms |
5076 KB |
Output is correct |
13 |
Correct |
4 ms |
5160 KB |
Output is correct |
14 |
Correct |
4 ms |
5204 KB |
Output is correct |
15 |
Correct |
160 ms |
19988 KB |
Output is correct |
16 |
Correct |
176 ms |
19584 KB |
Output is correct |
17 |
Correct |
158 ms |
19568 KB |
Output is correct |
18 |
Correct |
178 ms |
22220 KB |
Output is correct |
19 |
Correct |
154 ms |
21508 KB |
Output is correct |
20 |
Correct |
175 ms |
24524 KB |
Output is correct |
21 |
Correct |
149 ms |
19356 KB |
Output is correct |
22 |
Correct |
153 ms |
19004 KB |
Output is correct |
23 |
Correct |
171 ms |
18936 KB |
Output is correct |
24 |
Correct |
176 ms |
21924 KB |
Output is correct |
25 |
Correct |
149 ms |
25308 KB |
Output is correct |
26 |
Correct |
147 ms |
19536 KB |
Output is correct |
27 |
Correct |
150 ms |
19056 KB |
Output is correct |
28 |
Correct |
150 ms |
18968 KB |
Output is correct |
29 |
Correct |
212 ms |
21044 KB |
Output is correct |
30 |
Correct |
144 ms |
22480 KB |
Output is correct |
31 |
Correct |
151 ms |
19548 KB |
Output is correct |
32 |
Correct |
171 ms |
19160 KB |
Output is correct |
33 |
Correct |
157 ms |
19176 KB |
Output is correct |
34 |
Correct |
195 ms |
21836 KB |
Output is correct |
35 |
Correct |
150 ms |
25228 KB |
Output is correct |
36 |
Correct |
145 ms |
21584 KB |
Output is correct |