# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
260345 |
2020-08-10T06:17:40 Z |
arnold518 |
Valley (BOI19_valley) |
C++14 |
|
359 ms |
53496 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 = 1e18;
struct Edge
{
int u, v, w;
};
int N, S, Q, E;
Edge A[MAXN+10];
vector<pii> adj[MAXN+10];
bool P[MAXN+10];
int L[MAXN+10], R[MAXN+10], dep[MAXN+10], cnt, par[MAXN+10][30];
ll dist[MAXN+10], dp[MAXN+10][30];
void dfs(int now, int bef, int depp, ll distt)
{
dep[now]=depp;
dist[now]=distt;
L[now]=++cnt;
par[now][0]=bef;
dp[now][0]=INF;
if(P[now]) dp[now][0]=distt;
for(auto &nxt : adj[now])
{
if(nxt.first==bef) continue;
dfs(nxt.first, now, depp+1, distt+nxt.second);
dp[now][0]=min(dp[now][0], dp[nxt.first][0]);
}
R[now]=cnt;
}
int main()
{
scanf("%d%d%d%d", &N, &S, &Q, &E);
for(int 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});
A[i]={u, v, w};
}
for(int i=1; i<=S; i++)
{
int t;
scanf("%d", &t);
P[t]=1;
}
dfs(E, E, 1, 0);
for(int i=1; i<=N; i++) dp[i][0]-=2*dist[i];
for(int i=1; i<N; i++) if(dep[A[i].u]>dep[A[i].v]) swap(A[i].u, A[i].v);
for(int i=1; i<=20; i++) for(int j=1; j<=N; j++)
{
par[j][i]=par[par[j][i-1]][i-1];
dp[j][i]=min(dp[j][i-1], dp[par[j][i-1]][i-1]);
}
while(Q--)
{
int t, u;
scanf("%d%d", &t, &u);
int v=A[t].v;
if(!(L[v]<=L[u] && R[u]<=R[v])) printf("escaped\n");
else
{
ll val=1e17;
int now=u;
for(int i=20; i>=0; i--)
{
if(dep[par[now][i]]>=dep[v])
{
val=min(val, dp[now][i]);
now=par[now][i];
}
}
val=min(val, dp[v][0]);
if(val==(ll)1e17) printf("oo\n");
else printf("%lld\n", val+dist[u]);
}
}
}
Compilation message
valley.cpp: In function 'int main()':
valley.cpp:43: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:47: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:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &t);
~~~~~^~~~~~~~~~
valley.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &t, &u);
~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2816 KB |
Output is correct |
2 |
Correct |
7 ms |
2944 KB |
Output is correct |
3 |
Correct |
6 ms |
2944 KB |
Output is correct |
4 |
Correct |
6 ms |
2816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2816 KB |
Output is correct |
2 |
Correct |
7 ms |
2944 KB |
Output is correct |
3 |
Correct |
6 ms |
2944 KB |
Output is correct |
4 |
Correct |
6 ms |
2816 KB |
Output is correct |
5 |
Correct |
3 ms |
3200 KB |
Output is correct |
6 |
Correct |
3 ms |
3200 KB |
Output is correct |
7 |
Correct |
3 ms |
3200 KB |
Output is correct |
8 |
Correct |
3 ms |
3200 KB |
Output is correct |
9 |
Correct |
3 ms |
3200 KB |
Output is correct |
10 |
Correct |
4 ms |
3200 KB |
Output is correct |
11 |
Correct |
3 ms |
3200 KB |
Output is correct |
12 |
Correct |
4 ms |
3200 KB |
Output is correct |
13 |
Correct |
3 ms |
3200 KB |
Output is correct |
14 |
Correct |
3 ms |
3200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
224 ms |
45704 KB |
Output is correct |
2 |
Correct |
249 ms |
45368 KB |
Output is correct |
3 |
Correct |
250 ms |
45304 KB |
Output is correct |
4 |
Correct |
268 ms |
47096 KB |
Output is correct |
5 |
Correct |
242 ms |
47356 KB |
Output is correct |
6 |
Correct |
278 ms |
49016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2816 KB |
Output is correct |
2 |
Correct |
7 ms |
2944 KB |
Output is correct |
3 |
Correct |
6 ms |
2944 KB |
Output is correct |
4 |
Correct |
6 ms |
2816 KB |
Output is correct |
5 |
Correct |
3 ms |
3200 KB |
Output is correct |
6 |
Correct |
3 ms |
3200 KB |
Output is correct |
7 |
Correct |
3 ms |
3200 KB |
Output is correct |
8 |
Correct |
3 ms |
3200 KB |
Output is correct |
9 |
Correct |
3 ms |
3200 KB |
Output is correct |
10 |
Correct |
4 ms |
3200 KB |
Output is correct |
11 |
Correct |
3 ms |
3200 KB |
Output is correct |
12 |
Correct |
4 ms |
3200 KB |
Output is correct |
13 |
Correct |
3 ms |
3200 KB |
Output is correct |
14 |
Correct |
3 ms |
3200 KB |
Output is correct |
15 |
Correct |
224 ms |
45704 KB |
Output is correct |
16 |
Correct |
249 ms |
45368 KB |
Output is correct |
17 |
Correct |
250 ms |
45304 KB |
Output is correct |
18 |
Correct |
268 ms |
47096 KB |
Output is correct |
19 |
Correct |
242 ms |
47356 KB |
Output is correct |
20 |
Correct |
278 ms |
49016 KB |
Output is correct |
21 |
Correct |
204 ms |
49016 KB |
Output is correct |
22 |
Correct |
220 ms |
48632 KB |
Output is correct |
23 |
Correct |
225 ms |
48760 KB |
Output is correct |
24 |
Correct |
252 ms |
50552 KB |
Output is correct |
25 |
Correct |
259 ms |
53496 KB |
Output is correct |
26 |
Correct |
208 ms |
49016 KB |
Output is correct |
27 |
Correct |
216 ms |
48632 KB |
Output is correct |
28 |
Correct |
231 ms |
48712 KB |
Output is correct |
29 |
Correct |
283 ms |
50040 KB |
Output is correct |
30 |
Correct |
359 ms |
51448 KB |
Output is correct |
31 |
Correct |
269 ms |
49272 KB |
Output is correct |
32 |
Correct |
242 ms |
48760 KB |
Output is correct |
33 |
Correct |
253 ms |
48760 KB |
Output is correct |
34 |
Correct |
284 ms |
50564 KB |
Output is correct |
35 |
Correct |
274 ms |
53496 KB |
Output is correct |
36 |
Correct |
236 ms |
50808 KB |
Output is correct |