# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
310389 |
2020-10-06T20:17:03 Z |
rqi |
Valley (BOI19_valley) |
C++14 |
|
509 ms |
28408 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define f first
#define s second
#define pb push_back
#define mp make_pair
const int mx = 100005;
const ll INF = 1e18;
const ll BIG = 1e15;
int N, S, Q, E;
vector<pair<int, ll>> adj[mx];
int A[mx];
int B[mx];
ll W[mx];
bool isShop[mx];
int I[mx];
int R[mx];
bool esc[mx];
ll ans[mx];
vi queries[mx]; //queries at this node
bool inPath[mx];
void findPath(int node, int prv = -1){
inPath[node] = 1;
for(auto u: queries[node]){
if(!inPath[A[I[u]]] || !inPath[B[I[u]]]){
esc[u] = 1;
}
}
for(auto u: adj[node]){
if(u.f == prv) continue;
findPath(u.f, node);
}
inPath[node] = 0;
}
ll dist[mx];
int depth[mx];
ll shop[mx]; //lowest shop dist
void genDists(int node, ll cdist = 0, int cdepth = 0, int prv = -1){
dist[node] = cdist;
depth[node] = cdepth;
shop[node] = INF;
if(isShop[node]){
shop[node] = min(shop[node], dist[node]);
}
for(auto u: adj[node]){
if(u.f == prv) continue;
genDists(u.f, cdist+u.s, cdepth+1, node);
shop[node] = min(shop[node], shop[u.f]);
}
}
pair<int, ll> par[mx];
pair<int, ll> jmp[mx];
void genPar(int node, int prv = -1){
if(node == E){
par[node] = mp(node, INF);
jmp[node] = mp(node, INF);
}
else{
int p = par[node].f;
if(depth[p]-depth[jmp[p].f] == depth[jmp[p].f]-depth[jmp[jmp[p].f].f]){
jmp[node] = mp(jmp[jmp[p].f].f, min(par[node].s, min(jmp[p].s, jmp[jmp[p].f].s)));
}
else{
jmp[node] = par[node];
}
}
for(auto u: adj[node]){
if(u.f == prv) continue;
par[u.f] = mp(node, shop[node]);
genPar(u.f, node);
}
}
int main(){
cin >> N >> S >> Q >> E;
for(int i = 1; i < N; i++){
cin >> A[i] >> B[i] >> W[i];
adj[A[i]].pb(mp(B[i], W[i]));
adj[B[i]].pb(mp(A[i], W[i]));
}
for(int i = 1; i <= S; i++){
int C;
cin >> C;
isShop[C] = 1;
}
for(int i = 1; i <= Q; i++){
cin >> I[i] >> R[i];
queries[R[i]].pb(i);
}
findPath(E); //modify esc
genDists(E); //gen dist and depth
for(int i = 1; i <= N; i++){
shop[i]-=2*dist[i];
}
genPar(E);
for(int i = 1; i <= Q; i++){
if(esc[i]) continue;
int topnode = max(mp(depth[A[I[i]]], A[I[i]]), mp(depth[B[I[i]]], B[I[i]])).s;
int curnode = R[i];
ll curans = shop[R[i]];
while(curnode != topnode){
if(depth[jmp[curnode].f] >= depth[topnode]){
curans = min(curans, jmp[curnode].s);
curnode = jmp[curnode].f;
}
else{
curans = min(curans, par[curnode].s);
curnode = par[curnode].f;
}
}
ans[i] = curans+dist[R[i]];
}
for(int i = 1; i <= Q; i++){
if(esc[i]){
cout << "escaped" << "\n";
}
else{
if(ans[i] >= BIG){
cout << "oo" << "\n";
}
else{
cout << ans[i] << "\n";
}
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
5504 KB |
Output is correct |
2 |
Correct |
12 ms |
5504 KB |
Output is correct |
3 |
Correct |
12 ms |
5504 KB |
Output is correct |
4 |
Correct |
12 ms |
5504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
5504 KB |
Output is correct |
2 |
Correct |
12 ms |
5504 KB |
Output is correct |
3 |
Correct |
12 ms |
5504 KB |
Output is correct |
4 |
Correct |
12 ms |
5504 KB |
Output is correct |
5 |
Correct |
7 ms |
5248 KB |
Output is correct |
6 |
Correct |
7 ms |
5248 KB |
Output is correct |
7 |
Correct |
7 ms |
5248 KB |
Output is correct |
8 |
Correct |
7 ms |
5248 KB |
Output is correct |
9 |
Correct |
7 ms |
5248 KB |
Output is correct |
10 |
Correct |
7 ms |
5248 KB |
Output is correct |
11 |
Correct |
7 ms |
5248 KB |
Output is correct |
12 |
Correct |
7 ms |
5376 KB |
Output is correct |
13 |
Correct |
7 ms |
5248 KB |
Output is correct |
14 |
Correct |
6 ms |
5248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
475 ms |
25252 KB |
Output is correct |
2 |
Correct |
509 ms |
24952 KB |
Output is correct |
3 |
Correct |
489 ms |
25080 KB |
Output is correct |
4 |
Correct |
499 ms |
26744 KB |
Output is correct |
5 |
Correct |
469 ms |
25848 KB |
Output is correct |
6 |
Correct |
505 ms |
28152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
5504 KB |
Output is correct |
2 |
Correct |
12 ms |
5504 KB |
Output is correct |
3 |
Correct |
12 ms |
5504 KB |
Output is correct |
4 |
Correct |
12 ms |
5504 KB |
Output is correct |
5 |
Correct |
7 ms |
5248 KB |
Output is correct |
6 |
Correct |
7 ms |
5248 KB |
Output is correct |
7 |
Correct |
7 ms |
5248 KB |
Output is correct |
8 |
Correct |
7 ms |
5248 KB |
Output is correct |
9 |
Correct |
7 ms |
5248 KB |
Output is correct |
10 |
Correct |
7 ms |
5248 KB |
Output is correct |
11 |
Correct |
7 ms |
5248 KB |
Output is correct |
12 |
Correct |
7 ms |
5376 KB |
Output is correct |
13 |
Correct |
7 ms |
5248 KB |
Output is correct |
14 |
Correct |
6 ms |
5248 KB |
Output is correct |
15 |
Correct |
475 ms |
25252 KB |
Output is correct |
16 |
Correct |
509 ms |
24952 KB |
Output is correct |
17 |
Correct |
489 ms |
25080 KB |
Output is correct |
18 |
Correct |
499 ms |
26744 KB |
Output is correct |
19 |
Correct |
469 ms |
25848 KB |
Output is correct |
20 |
Correct |
505 ms |
28152 KB |
Output is correct |
21 |
Correct |
414 ms |
24632 KB |
Output is correct |
22 |
Correct |
427 ms |
24440 KB |
Output is correct |
23 |
Correct |
433 ms |
24312 KB |
Output is correct |
24 |
Correct |
449 ms |
26488 KB |
Output is correct |
25 |
Correct |
442 ms |
28408 KB |
Output is correct |
26 |
Correct |
410 ms |
24696 KB |
Output is correct |
27 |
Correct |
424 ms |
24472 KB |
Output is correct |
28 |
Correct |
437 ms |
24468 KB |
Output is correct |
29 |
Correct |
450 ms |
25848 KB |
Output is correct |
30 |
Correct |
449 ms |
26488 KB |
Output is correct |
31 |
Correct |
408 ms |
24824 KB |
Output is correct |
32 |
Correct |
428 ms |
24568 KB |
Output is correct |
33 |
Correct |
448 ms |
24824 KB |
Output is correct |
34 |
Correct |
455 ms |
26360 KB |
Output is correct |
35 |
Correct |
440 ms |
28408 KB |
Output is correct |
36 |
Correct |
408 ms |
26104 KB |
Output is correct |