# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
153033 |
2019-09-11T14:18:57 Z |
abacaba |
Valley (BOI19_valley) |
C++14 |
|
389 ms |
40772 KB |
#include <iostream>
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <random>
#include <bitset>
#include <string>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <stack>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
struct edge {
int u, v, w;
};
const ll inf = 2e18;
const int N = 1e5 + 15;
const int L = 20;
int n, s, q, t, tin[N], tout[N], last, up[L][N];
ll minn[N], d[N], dp[L][N];
vector <int> g[N];
vector <edge> e;
bool is[N];
inline bool upper(int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
void build(int v, int p = t) {
tin[v] = ++last;
up[0][v] = p;
for(int i = 1; i < L; ++i)
up[i][v] = up[i-1][up[i-1][v]];
if(is[v])
minn[v] = d[v];
for(int i : g[v]) {
int to = (e[i].u == v ? e[i].v : e[i].u), w = e[i].w;
if(to != p) {
d[to] = d[v] + w;
build(to, v);
minn[v] = min(minn[v], minn[to]);
}
}
tout[v] = ++last;
}
void build_dp(int v, int p = t) {
dp[0][v] = minn[v];
for(int i = 1; i < L; ++i)
dp[i][v] = min(dp[i-1][v], dp[i-1][up[i-1][v]]);
for(int i : g[v]) {
int to = (e[i].u == v ? e[i].v : e[i].u);
if(to != p)
build_dp(to, v);
}
}
inline ll get_lowest(int a, int b) {
ll res = inf;
for(int i = L - 1; i >= 0; --i)
if(upper(a, up[i][b])) {
res = min(res, dp[i][b]);
b = up[i][b];
}
return min(res, dp[0][b]);
}
int main() {
fill(minn, minn + N, inf);
for(int i = 0; i < L; ++i)
fill(dp[i], dp[i] + N, inf);
scanf("%d%d%d%d", &n, &s, &q, &t);
for(int i = 1; i < n; ++i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
e.pb({u, v, w});
g[u].pb(e.size() - 1);
g[v].pb(e.size() - 1);
}
for(int i = 1; i <= s; ++i) {
int x;
scanf("%d", &x);
is[x] = true;
}
build(t);
for(int i = 1; i <= n; ++i) {
if(minn[i] != inf)
minn[i] -= 2LL * d[i];
}
build_dp(t);
while(q--) {
int i, x;
scanf("%d%d", &i, &x);
int u = e[i - 1].u, v = e[i - 1].v;
if(tin[u] > tin[v])
swap(u, v);
if(!upper(v, x)) {
puts("escaped");
continue;
}
ll val = get_lowest(v, x);
if(val < inf)
printf("%lld\n", val + d[x]);
else
puts("oo");
}
return 0;
}
Compilation message
valley.cpp: In function 'int main()':
valley.cpp:97:10: 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, &t);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:100:11: 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:107:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
valley.cpp:118:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &i, &x);
~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
19320 KB |
Output is correct |
2 |
Correct |
20 ms |
19320 KB |
Output is correct |
3 |
Correct |
66 ms |
19448 KB |
Output is correct |
4 |
Correct |
23 ms |
19320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
19320 KB |
Output is correct |
2 |
Correct |
20 ms |
19320 KB |
Output is correct |
3 |
Correct |
66 ms |
19448 KB |
Output is correct |
4 |
Correct |
23 ms |
19320 KB |
Output is correct |
5 |
Correct |
21 ms |
19372 KB |
Output is correct |
6 |
Correct |
20 ms |
19336 KB |
Output is correct |
7 |
Correct |
22 ms |
19448 KB |
Output is correct |
8 |
Correct |
22 ms |
19320 KB |
Output is correct |
9 |
Correct |
19 ms |
19420 KB |
Output is correct |
10 |
Correct |
19 ms |
19320 KB |
Output is correct |
11 |
Correct |
19 ms |
19380 KB |
Output is correct |
12 |
Correct |
19 ms |
19448 KB |
Output is correct |
13 |
Correct |
18 ms |
19448 KB |
Output is correct |
14 |
Correct |
19 ms |
19448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
303 ms |
33772 KB |
Output is correct |
2 |
Correct |
326 ms |
33600 KB |
Output is correct |
3 |
Correct |
336 ms |
33476 KB |
Output is correct |
4 |
Correct |
388 ms |
34916 KB |
Output is correct |
5 |
Correct |
345 ms |
34984 KB |
Output is correct |
6 |
Correct |
389 ms |
36656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
19320 KB |
Output is correct |
2 |
Correct |
20 ms |
19320 KB |
Output is correct |
3 |
Correct |
66 ms |
19448 KB |
Output is correct |
4 |
Correct |
23 ms |
19320 KB |
Output is correct |
5 |
Correct |
21 ms |
19372 KB |
Output is correct |
6 |
Correct |
20 ms |
19336 KB |
Output is correct |
7 |
Correct |
22 ms |
19448 KB |
Output is correct |
8 |
Correct |
22 ms |
19320 KB |
Output is correct |
9 |
Correct |
19 ms |
19420 KB |
Output is correct |
10 |
Correct |
19 ms |
19320 KB |
Output is correct |
11 |
Correct |
19 ms |
19380 KB |
Output is correct |
12 |
Correct |
19 ms |
19448 KB |
Output is correct |
13 |
Correct |
18 ms |
19448 KB |
Output is correct |
14 |
Correct |
19 ms |
19448 KB |
Output is correct |
15 |
Correct |
303 ms |
33772 KB |
Output is correct |
16 |
Correct |
326 ms |
33600 KB |
Output is correct |
17 |
Correct |
336 ms |
33476 KB |
Output is correct |
18 |
Correct |
388 ms |
34916 KB |
Output is correct |
19 |
Correct |
345 ms |
34984 KB |
Output is correct |
20 |
Correct |
389 ms |
36656 KB |
Output is correct |
21 |
Correct |
278 ms |
37048 KB |
Output is correct |
22 |
Correct |
293 ms |
36744 KB |
Output is correct |
23 |
Correct |
301 ms |
36816 KB |
Output is correct |
24 |
Correct |
348 ms |
38316 KB |
Output is correct |
25 |
Correct |
380 ms |
40772 KB |
Output is correct |
26 |
Correct |
283 ms |
37264 KB |
Output is correct |
27 |
Correct |
295 ms |
36904 KB |
Output is correct |
28 |
Correct |
303 ms |
36864 KB |
Output is correct |
29 |
Correct |
338 ms |
38040 KB |
Output is correct |
30 |
Correct |
343 ms |
39212 KB |
Output is correct |
31 |
Correct |
279 ms |
37132 KB |
Output is correct |
32 |
Correct |
293 ms |
37032 KB |
Output is correct |
33 |
Correct |
313 ms |
37032 KB |
Output is correct |
34 |
Correct |
335 ms |
38440 KB |
Output is correct |
35 |
Correct |
341 ms |
40748 KB |
Output is correct |
36 |
Correct |
319 ms |
38184 KB |
Output is correct |