# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
674649 |
2022-12-25T15:10:41 Z |
AmirH |
Valley (BOI19_valley) |
C++14 |
|
193 ms |
68288 KB |
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<bitset>
#include<queue>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<unordered_map>
#include<list>
#include<utility>
#include<stack>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
#define cl clear
#define F first
#define S second
#define pb push_back
#define Sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define faster ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
const int MAX_N = 2e5 + 25;
const ll INF = 1e18;
const int inf = 1e9;
const int lgg = 20;
int n, s, q, e;
vector<pii> adj[MAX_N];
bool mark[MAX_N];
int par[MAX_N];
ll magic[MAX_N];
ll dist[MAX_N];
int height[MAX_N];
ll lift[MAX_N][lgg + 10];
ll lift_min[MAX_N][lgg + 10];
vector<pii> edge;
int baz[MAX_N];
int bas[MAX_N];
int d = 0;
void free() {
#ifndef ONLINE_JUDGE
freopen("inputi.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
}
void build_lift() {
for(int i = 1; i <= n; i++) {
lift[i][0] = i;
lift_min[i][0] = magic[i];
}
for(int i = 1; i <= lgg; i++) {
for(int j = 1; j <= n; j++) {
if((1 << (i - 1)) <= height[j]) {
if(i == 1) {
lift[j][i] = par[j];
lift_min[j][i] = min(magic[j], magic[par[j]]);
}
else {
lift[j][i] = lift[lift[j][i - 1]][i - 1];
lift_min[j][i] = min(lift_min[lift[j][i - 1]][i - 1], lift_min[j][i - 1]);
}
}
}
}
}
ll get_min(int v, int h) {
if(!h)
return magic[v];
int chap = 31 - __builtin_clz(h);
return min(lift_min[v][chap + 1], get_min(lift[v][chap + 1], h - (1 << chap)));
}
void sfd(int v, int s) {
if(mark[v])
magic[v] = dist[v];
else
magic[v] = INF;
for(auto i : adj[v]) {
if(i.first != s) {
sfd(i.first, v);
magic[v] = min(magic[v], magic[i.first]);
}
}
}
void dfs(int v, int s) {
d++;
baz[v] = d;
for(auto i : adj[v]) {
if(i.first != s) {
par[i.first] = v;
dist[i.first] = dist[v] + i.second;
height[i.first] = height[v] + 1;
dfs(i.first, v);
}
}
d++;
bas[v] = d;
}
void input() {
cin >> n >> s >> q >> e;
for(int i = 1; i < n; i++) {
int x, y, z; cin >> x >> y >> z;
adj[x].pb({y, z});
adj[y].pb({x, z});
edge.pb({x, y});
}
for(int i = 1; i <= s; i++) {
int x; cin >> x;
mark[x] = true;
}
}
void solve() {
par[e] = 0;
dist[e] = 0;
height[e] = 0;
dfs(e, 0);
sfd(e, 0);
for(int i = 1; i <= n; i++)
magic[i] -= (2 * dist[i]);
build_lift();
}
void output() {
while(q--) {
int l, y; cin >> l >> y;
l--;
int x;
if(height[edge[l].first] > height[edge[l].second])
x = edge[l].first;
else
x = edge[l].second;
if(baz[x] <= baz[y] && bas[x] >= bas[y]) {
ll res = get_min(y, height[y] - height[x]) + dist[y];
if(res > 1e15)
cout << "oo" << '\n';
else
cout << res << '\n';
}
else {
cout << "escaped" << '\n';
}
}
}
int main() {
faster; //free();
input();
solve();
output();
}
Compilation message
valley.cpp: In function 'void free()':
valley.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | freopen("inputi.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | freopen("out.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5204 KB |
Output is correct |
2 |
Correct |
5 ms |
5172 KB |
Output is correct |
3 |
Correct |
5 ms |
5204 KB |
Output is correct |
4 |
Correct |
5 ms |
5176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5204 KB |
Output is correct |
2 |
Correct |
5 ms |
5172 KB |
Output is correct |
3 |
Correct |
5 ms |
5204 KB |
Output is correct |
4 |
Correct |
5 ms |
5176 KB |
Output is correct |
5 |
Correct |
5 ms |
5556 KB |
Output is correct |
6 |
Correct |
4 ms |
5552 KB |
Output is correct |
7 |
Correct |
4 ms |
5588 KB |
Output is correct |
8 |
Correct |
3 ms |
5560 KB |
Output is correct |
9 |
Correct |
3 ms |
5588 KB |
Output is correct |
10 |
Correct |
4 ms |
5600 KB |
Output is correct |
11 |
Correct |
4 ms |
5552 KB |
Output is correct |
12 |
Correct |
4 ms |
5556 KB |
Output is correct |
13 |
Correct |
4 ms |
5560 KB |
Output is correct |
14 |
Correct |
3 ms |
5568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
61408 KB |
Output is correct |
2 |
Correct |
137 ms |
61160 KB |
Output is correct |
3 |
Correct |
142 ms |
60992 KB |
Output is correct |
4 |
Correct |
170 ms |
62784 KB |
Output is correct |
5 |
Correct |
154 ms |
62804 KB |
Output is correct |
6 |
Correct |
187 ms |
64700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5204 KB |
Output is correct |
2 |
Correct |
5 ms |
5172 KB |
Output is correct |
3 |
Correct |
5 ms |
5204 KB |
Output is correct |
4 |
Correct |
5 ms |
5176 KB |
Output is correct |
5 |
Correct |
5 ms |
5556 KB |
Output is correct |
6 |
Correct |
4 ms |
5552 KB |
Output is correct |
7 |
Correct |
4 ms |
5588 KB |
Output is correct |
8 |
Correct |
3 ms |
5560 KB |
Output is correct |
9 |
Correct |
3 ms |
5588 KB |
Output is correct |
10 |
Correct |
4 ms |
5600 KB |
Output is correct |
11 |
Correct |
4 ms |
5552 KB |
Output is correct |
12 |
Correct |
4 ms |
5556 KB |
Output is correct |
13 |
Correct |
4 ms |
5560 KB |
Output is correct |
14 |
Correct |
3 ms |
5568 KB |
Output is correct |
15 |
Correct |
114 ms |
61408 KB |
Output is correct |
16 |
Correct |
137 ms |
61160 KB |
Output is correct |
17 |
Correct |
142 ms |
60992 KB |
Output is correct |
18 |
Correct |
170 ms |
62784 KB |
Output is correct |
19 |
Correct |
154 ms |
62804 KB |
Output is correct |
20 |
Correct |
187 ms |
64700 KB |
Output is correct |
21 |
Correct |
104 ms |
63836 KB |
Output is correct |
22 |
Correct |
116 ms |
63420 KB |
Output is correct |
23 |
Correct |
135 ms |
63396 KB |
Output is correct |
24 |
Correct |
165 ms |
65468 KB |
Output is correct |
25 |
Correct |
167 ms |
68288 KB |
Output is correct |
26 |
Correct |
108 ms |
63904 KB |
Output is correct |
27 |
Correct |
120 ms |
63512 KB |
Output is correct |
28 |
Correct |
130 ms |
63480 KB |
Output is correct |
29 |
Correct |
169 ms |
64940 KB |
Output is correct |
30 |
Correct |
193 ms |
66384 KB |
Output is correct |
31 |
Correct |
104 ms |
63956 KB |
Output is correct |
32 |
Correct |
121 ms |
63644 KB |
Output is correct |
33 |
Correct |
146 ms |
63640 KB |
Output is correct |
34 |
Correct |
170 ms |
65476 KB |
Output is correct |
35 |
Correct |
170 ms |
68264 KB |
Output is correct |
36 |
Correct |
154 ms |
65580 KB |
Output is correct |