# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
197044 |
2020-01-18T09:52:24 Z |
arnold518 |
Valley (BOI19_valley) |
C++14 |
|
338 ms |
60280 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const ll INF = 1e15;
struct Edge { int u, v, w; };
int N, S, Q, E;
vector<pii> adj[MAXN+10];
Edge edge[MAXN+10];
int C[MAXN+10];
int L[MAXN+10], R[MAXN+10], cnt, par[MAXN+10][35], dep[MAXN+10];
ll D[MAXN+10], EE[MAXN+10][35], F[MAXN+10];
bool reach(int I, int u, int v)
{
bool a=(L[edge[I].v]<=L[u] && L[u]<=R[edge[I].v]);
bool b=(L[edge[I].v]<=L[v] && L[v]<=R[edge[I].v]);
return a==b;
}
void dfs(int now, int bef, ll dist, int depp)
{
par[now][0]=bef;
L[now]=R[now]=++cnt;
D[now]=10*INF;
if(C[now]) D[now]=dist;
dep[now]=depp;
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
dfs(nxt.first, now, dist+nxt.second, depp+1);
R[now]=max(R[now], R[nxt.first]);
D[now]=min(D[now], D[nxt.first]);
}
F[now]=dist;
EE[now][0]=D[now]-2*dist;
//printf("%d : %lld\n", now, EE[now][0]);
}
int main()
{
int i, j;
scanf("%d%d%d%d", &N, &S, &Q, &E);
for(i=1; i<N; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
adj[u].push_back({v, w});
adj[v].push_back({u, w});
edge[i]={u, v, w};
}
for(i=1; i<=S; i++)
{
int t;
scanf("%d", &t);
C[t]=1;
}
dfs(E, E, 0, 1);
for(i=1; i<N; i++) if(L[edge[i].u]>L[edge[i].v]) swap(edge[i].u, edge[i].v);
for(i=1; i<=20; i++) for(j=1; j<=N; j++) par[j][i]=par[par[j][i-1]][i-1], EE[j][i]=min(EE[j][i-1], EE[par[j][i-1]][i-1]);
while(Q--)
{
int A, B;
scanf("%d%d", &A, &B);
if(reach(A, E, B)) { printf("escaped\n"); continue; }
int now=B, to=edge[A].v;
//printf("%d %d\n", now, to);
ll ans=INF;
if(C[now]) ans=0;
for(i=20; i>=0; i--)
{
//printf("%d %d\n", par[now][i], i);
if(dep[par[now][i]]>=dep[to])
{
ans=min(ans, EE[now][i]+F[B]);
now=par[now][i];
}
}
ans=min(ans, EE[to][0]+F[B]);
if(ans==INF) printf("oo\n");
else printf("%lld\n", ans);
}
}
Compilation message
valley.cpp: In function 'int main()':
valley.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &N, &S, &Q, &E);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &u, &v, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &t);
~~~~~^~~~~~~~~~
valley.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &A, &B);
~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2808 KB |
Output is correct |
2 |
Correct |
7 ms |
2808 KB |
Output is correct |
3 |
Correct |
7 ms |
2936 KB |
Output is correct |
4 |
Correct |
8 ms |
2936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2808 KB |
Output is correct |
2 |
Correct |
7 ms |
2808 KB |
Output is correct |
3 |
Correct |
7 ms |
2936 KB |
Output is correct |
4 |
Correct |
8 ms |
2936 KB |
Output is correct |
5 |
Correct |
6 ms |
3320 KB |
Output is correct |
6 |
Correct |
9 ms |
3320 KB |
Output is correct |
7 |
Correct |
6 ms |
3320 KB |
Output is correct |
8 |
Correct |
6 ms |
3192 KB |
Output is correct |
9 |
Correct |
3 ms |
3320 KB |
Output is correct |
10 |
Correct |
5 ms |
3268 KB |
Output is correct |
11 |
Correct |
6 ms |
3192 KB |
Output is correct |
12 |
Correct |
5 ms |
3320 KB |
Output is correct |
13 |
Correct |
7 ms |
3320 KB |
Output is correct |
14 |
Correct |
6 ms |
3320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
280 ms |
52732 KB |
Output is correct |
2 |
Correct |
280 ms |
52380 KB |
Output is correct |
3 |
Correct |
294 ms |
52244 KB |
Output is correct |
4 |
Correct |
306 ms |
54188 KB |
Output is correct |
5 |
Correct |
297 ms |
54264 KB |
Output is correct |
6 |
Correct |
328 ms |
56056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2808 KB |
Output is correct |
2 |
Correct |
7 ms |
2808 KB |
Output is correct |
3 |
Correct |
7 ms |
2936 KB |
Output is correct |
4 |
Correct |
8 ms |
2936 KB |
Output is correct |
5 |
Correct |
6 ms |
3320 KB |
Output is correct |
6 |
Correct |
9 ms |
3320 KB |
Output is correct |
7 |
Correct |
6 ms |
3320 KB |
Output is correct |
8 |
Correct |
6 ms |
3192 KB |
Output is correct |
9 |
Correct |
3 ms |
3320 KB |
Output is correct |
10 |
Correct |
5 ms |
3268 KB |
Output is correct |
11 |
Correct |
6 ms |
3192 KB |
Output is correct |
12 |
Correct |
5 ms |
3320 KB |
Output is correct |
13 |
Correct |
7 ms |
3320 KB |
Output is correct |
14 |
Correct |
6 ms |
3320 KB |
Output is correct |
15 |
Correct |
280 ms |
52732 KB |
Output is correct |
16 |
Correct |
280 ms |
52380 KB |
Output is correct |
17 |
Correct |
294 ms |
52244 KB |
Output is correct |
18 |
Correct |
306 ms |
54188 KB |
Output is correct |
19 |
Correct |
297 ms |
54264 KB |
Output is correct |
20 |
Correct |
328 ms |
56056 KB |
Output is correct |
21 |
Correct |
255 ms |
55716 KB |
Output is correct |
22 |
Correct |
290 ms |
55288 KB |
Output is correct |
23 |
Correct |
283 ms |
55160 KB |
Output is correct |
24 |
Correct |
330 ms |
57336 KB |
Output is correct |
25 |
Correct |
299 ms |
60092 KB |
Output is correct |
26 |
Correct |
338 ms |
56056 KB |
Output is correct |
27 |
Correct |
257 ms |
55672 KB |
Output is correct |
28 |
Correct |
268 ms |
55492 KB |
Output is correct |
29 |
Correct |
289 ms |
57020 KB |
Output is correct |
30 |
Correct |
302 ms |
58232 KB |
Output is correct |
31 |
Correct |
253 ms |
56208 KB |
Output is correct |
32 |
Correct |
259 ms |
55752 KB |
Output is correct |
33 |
Correct |
274 ms |
55800 KB |
Output is correct |
34 |
Correct |
299 ms |
57592 KB |
Output is correct |
35 |
Correct |
283 ms |
60280 KB |
Output is correct |
36 |
Correct |
282 ms |
57720 KB |
Output is correct |