# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
873780 |
2023-11-15T18:21:58 Z |
hqminhuwu |
Valley (BOI19_valley) |
C++14 |
|
128 ms |
145792 KB |
#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"
using namespace std;
const int N = 5e5 + 5;
const ll oo = 1e17;
const ll mod = 1e9 + 7;
ll bg[N],ed[N],dp[N],dep[N],d[N],up[20][N],updp[20][N],cnt;
vector <pll> a[N],edge;
void dfs (int u, int p){
bg[u] = ++cnt;
for (pii k : a[u]){
int w = k.nd, v = k.st;
if (v == p) continue;
dep[v] = dep[u] + 1;
d[v] = d[u] + w;
up[0][v] = u;
dfs(v,u);
dp[u] = min (dp[u],dp[v] + w);
}
ed[u] = cnt;
}
void dfs1 (int u, int p){
for (pii k : a[u]){
int w = k.nd, v = k.st;
if (v == p) continue;
updp[0][v] = dp[u] - d[u];
dfs1(v,u);
}
}
bool anc (int u, int v){
return (bg[u] <= bg[v]) && (ed[u] >= ed[v]);
}
ll jump (int u, int v) {
ll ans = oo,i;
ford (i,18,0)
if (v & (1 << i)){
ans = min(ans, updp[i][u]);
u = up[i][u];
}
return ans;
}
ll n,s,q,e,i,j,u,v,w;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> s >> q >> e;
forf (i,1,n) {
cin >> u >> v >> w;
edge.pb({u, v});
a[u].pb({v, w});
a[v].pb({u, w});
}
forr (j,0,18)
forr (i,1,n)
updp[j][i] = oo;
forr (i,1,n)
dp[i] = oo;
forr (i,1,s)
cin >> u, dp[u] = 0;
dfs(e,e);
dfs1(e,e);
forr (j,1,18)
forr (i,1,n)
up[j][i] = up[j - 1][up[j - 1][i]],
updp[j][i] = min(updp[j - 1][i],updp[j - 1][up[j - 1][i]]);
forf (i,0,n - 1)
if (d[edge[i].st] < d[edge[i].nd])
swap(edge[i].st, edge[i].nd);
while (q--){
cin >> i >> u;
int v = edge[i - 1].st;
if (!anc(v,u)){
cout << "escaped\n";
continue;
}
if (dp[v] == oo){
cout << "oo\n";
continue;
}
cout << min (d[u] + jump(u,dep[u] - dep[v]),dp[u]) << "\n";
}
return 0;
}
/*
*/
Compilation message
valley.cpp: In function 'void dfs1(int, int)':
valley.cpp:42:13: warning: unused variable 'w' [-Wunused-variable]
42 | int w = k.nd, v = k.st;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
95320 KB |
Output is correct |
2 |
Correct |
13 ms |
95060 KB |
Output is correct |
3 |
Correct |
12 ms |
95064 KB |
Output is correct |
4 |
Correct |
13 ms |
95192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
95320 KB |
Output is correct |
2 |
Correct |
13 ms |
95060 KB |
Output is correct |
3 |
Correct |
12 ms |
95064 KB |
Output is correct |
4 |
Correct |
13 ms |
95192 KB |
Output is correct |
5 |
Correct |
12 ms |
95068 KB |
Output is correct |
6 |
Correct |
12 ms |
95068 KB |
Output is correct |
7 |
Correct |
12 ms |
95068 KB |
Output is correct |
8 |
Correct |
12 ms |
95064 KB |
Output is correct |
9 |
Correct |
12 ms |
95064 KB |
Output is correct |
10 |
Correct |
13 ms |
95112 KB |
Output is correct |
11 |
Correct |
12 ms |
95068 KB |
Output is correct |
12 |
Correct |
12 ms |
95068 KB |
Output is correct |
13 |
Correct |
12 ms |
95140 KB |
Output is correct |
14 |
Correct |
12 ms |
95320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
99 ms |
135612 KB |
Output is correct |
2 |
Correct |
91 ms |
136124 KB |
Output is correct |
3 |
Correct |
98 ms |
135612 KB |
Output is correct |
4 |
Correct |
114 ms |
138432 KB |
Output is correct |
5 |
Correct |
98 ms |
138684 KB |
Output is correct |
6 |
Correct |
125 ms |
141244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
95320 KB |
Output is correct |
2 |
Correct |
13 ms |
95060 KB |
Output is correct |
3 |
Correct |
12 ms |
95064 KB |
Output is correct |
4 |
Correct |
13 ms |
95192 KB |
Output is correct |
5 |
Correct |
12 ms |
95068 KB |
Output is correct |
6 |
Correct |
12 ms |
95068 KB |
Output is correct |
7 |
Correct |
12 ms |
95068 KB |
Output is correct |
8 |
Correct |
12 ms |
95064 KB |
Output is correct |
9 |
Correct |
12 ms |
95064 KB |
Output is correct |
10 |
Correct |
13 ms |
95112 KB |
Output is correct |
11 |
Correct |
12 ms |
95068 KB |
Output is correct |
12 |
Correct |
12 ms |
95068 KB |
Output is correct |
13 |
Correct |
12 ms |
95140 KB |
Output is correct |
14 |
Correct |
12 ms |
95320 KB |
Output is correct |
15 |
Correct |
99 ms |
135612 KB |
Output is correct |
16 |
Correct |
91 ms |
136124 KB |
Output is correct |
17 |
Correct |
98 ms |
135612 KB |
Output is correct |
18 |
Correct |
114 ms |
138432 KB |
Output is correct |
19 |
Correct |
98 ms |
138684 KB |
Output is correct |
20 |
Correct |
125 ms |
141244 KB |
Output is correct |
21 |
Correct |
76 ms |
139796 KB |
Output is correct |
22 |
Correct |
83 ms |
139316 KB |
Output is correct |
23 |
Correct |
85 ms |
139452 KB |
Output is correct |
24 |
Correct |
94 ms |
142048 KB |
Output is correct |
25 |
Correct |
122 ms |
145792 KB |
Output is correct |
26 |
Correct |
77 ms |
139528 KB |
Output is correct |
27 |
Correct |
84 ms |
139304 KB |
Output is correct |
28 |
Correct |
92 ms |
139452 KB |
Output is correct |
29 |
Correct |
107 ms |
141276 KB |
Output is correct |
30 |
Correct |
121 ms |
143292 KB |
Output is correct |
31 |
Correct |
79 ms |
139608 KB |
Output is correct |
32 |
Correct |
103 ms |
139476 KB |
Output is correct |
33 |
Correct |
90 ms |
139712 KB |
Output is correct |
34 |
Correct |
128 ms |
142008 KB |
Output is correct |
35 |
Correct |
110 ms |
144832 KB |
Output is correct |
36 |
Correct |
106 ms |
142012 KB |
Output is correct |