# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
516338 |
2022-01-21T06:41:49 Z |
kingline |
Valley (BOI19_valley) |
C++17 |
|
232 ms |
54488 KB |
/*#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")*/
#include <bits/stdc++.h>
#define file(data) freopen(data".in", "r", stdin); freopen(data".out", "w", stdout);
#define pb push_back
//#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(data) data.begin() , data.end()
#define endl '\n'
//freopen("nenokku_easy.in", "r", stdin);
//freopen("nenokku_easy.out", "w", stdout);
#define int long long
#define pii pair < int, int >
#define pll pair < long long, long long >
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int M = 305;
const int mod = 1e9 + 7;
const ll INF = 1e18;
const int lg = 20;
const long double limit = 1.0;
int n, s, q, e, tin[N], tout[N], a[N], b[N], w[N], h[N], d[N], dist[N], up[N][lg], mn[N][lg];
bool shop[N];
vector < pair < int, int > > g[N];
int sz;
void dfs(int v, int pr) {
if(shop[v]) d[v] = 0;
else d[v] = INF;
tin[v] = ++sz;
h[v] = h[pr] + 1;
for(int i = 0; i < g[v].size(); i++) {
int to = g[v][i].first, len = g[v][i].second;
if(to != pr) {
dist[to] = dist[v] + len;
dfs(to, v);
d[v] = min(d[v], d[to] + len);
}
}
tout[v] = sz;
}
void dfs2(int v, int pr) {
up[v][0] = pr;
mn[v][0] = min(-dist[v] + d[v], -dist[pr] + d[pr]);
for(int i = 1; i < lg; i++) {
mn[v][i] = min(mn[v][i - 1], mn[up[v][i - 1]][i - 1]);
up[v][i] = up[up[v][i - 1]][i - 1];
}
for(int i = 0; i < g[v].size(); i++) {
int to = g[v][i].first, len = g[v][i].second;
if(to != pr) {
dfs2(to, v);
}
}
}
bool upper(int x, int y) {
return tin[x] <= tin[y] && tout[x] >= tout[y];
}
int get(int anc, int x) {
int res = -dist[x] + d[x];
for(int i = lg - 1; i >= 0; i--) {
if(!upper(up[x][i], anc)) {
res = min(res, mn[x][i]);
x = up[x][i];
}
}
if(x != anc) {
res = min(res, mn[x][0]);
}
return res;
}
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//file("threesum");
cin >> n >> s >> q >> e;
for(int i = 1; i < n; i++) {
cin >> a[i] >> b[i] >> w[i];
g[a[i]].pb({b[i], w[i]});
g[b[i]].pb({a[i], w[i]});
}
for(int i = 1; i <= s; i++) {
int z; cin >> z;
shop[z] = 1;
}
dfs(e, e);
dfs2(e, e);
while(q--) {
int block, now;
cin >> block >> now;
if(h[a[block]] > h[b[block]]) swap(a[block], b[block]);
if(!upper(b[block], now)) {
cout << "escaped\n";
} else if(d[b[block]] == INF) {
cout << "oo\n";
} else {
if(shop[now]) cout << "0\n";
else {
cout << dist[now] + get(b[block], now) << endl;
}
}
}
}
Compilation message
valley.cpp: In function 'void dfs(long long int, long long int)':
valley.cpp:39:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i = 0; i < g[v].size(); i++) {
| ~~^~~~~~~~~~~~~
valley.cpp: In function 'void dfs2(long long int, long long int)':
valley.cpp:57:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int i = 0; i < g[v].size(); i++) {
| ~~^~~~~~~~~~~~~
valley.cpp:58:33: warning: unused variable 'len' [-Wunused-variable]
58 | int to = g[v][i].first, len = g[v][i].second;
| ^~~
valley.cpp: At global scope:
valley.cpp:83:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
83 | main() {
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2824 KB |
Output is correct |
2 |
Correct |
5 ms |
2816 KB |
Output is correct |
3 |
Correct |
3 ms |
2816 KB |
Output is correct |
4 |
Correct |
3 ms |
2892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2824 KB |
Output is correct |
2 |
Correct |
5 ms |
2816 KB |
Output is correct |
3 |
Correct |
3 ms |
2816 KB |
Output is correct |
4 |
Correct |
3 ms |
2892 KB |
Output is correct |
5 |
Correct |
2 ms |
3148 KB |
Output is correct |
6 |
Correct |
2 ms |
3148 KB |
Output is correct |
7 |
Correct |
2 ms |
3148 KB |
Output is correct |
8 |
Correct |
2 ms |
3148 KB |
Output is correct |
9 |
Correct |
2 ms |
3148 KB |
Output is correct |
10 |
Correct |
3 ms |
3196 KB |
Output is correct |
11 |
Correct |
3 ms |
3196 KB |
Output is correct |
12 |
Correct |
2 ms |
3192 KB |
Output is correct |
13 |
Correct |
2 ms |
3148 KB |
Output is correct |
14 |
Correct |
2 ms |
3196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
133 ms |
49844 KB |
Output is correct |
2 |
Correct |
162 ms |
49852 KB |
Output is correct |
3 |
Correct |
201 ms |
49932 KB |
Output is correct |
4 |
Correct |
171 ms |
51852 KB |
Output is correct |
5 |
Correct |
165 ms |
51964 KB |
Output is correct |
6 |
Correct |
175 ms |
54112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2824 KB |
Output is correct |
2 |
Correct |
5 ms |
2816 KB |
Output is correct |
3 |
Correct |
3 ms |
2816 KB |
Output is correct |
4 |
Correct |
3 ms |
2892 KB |
Output is correct |
5 |
Correct |
2 ms |
3148 KB |
Output is correct |
6 |
Correct |
2 ms |
3148 KB |
Output is correct |
7 |
Correct |
2 ms |
3148 KB |
Output is correct |
8 |
Correct |
2 ms |
3148 KB |
Output is correct |
9 |
Correct |
2 ms |
3148 KB |
Output is correct |
10 |
Correct |
3 ms |
3196 KB |
Output is correct |
11 |
Correct |
3 ms |
3196 KB |
Output is correct |
12 |
Correct |
2 ms |
3192 KB |
Output is correct |
13 |
Correct |
2 ms |
3148 KB |
Output is correct |
14 |
Correct |
2 ms |
3196 KB |
Output is correct |
15 |
Correct |
133 ms |
49844 KB |
Output is correct |
16 |
Correct |
162 ms |
49852 KB |
Output is correct |
17 |
Correct |
201 ms |
49932 KB |
Output is correct |
18 |
Correct |
171 ms |
51852 KB |
Output is correct |
19 |
Correct |
165 ms |
51964 KB |
Output is correct |
20 |
Correct |
175 ms |
54112 KB |
Output is correct |
21 |
Correct |
156 ms |
49376 KB |
Output is correct |
22 |
Correct |
148 ms |
49124 KB |
Output is correct |
23 |
Correct |
154 ms |
49356 KB |
Output is correct |
24 |
Correct |
171 ms |
51432 KB |
Output is correct |
25 |
Correct |
211 ms |
54420 KB |
Output is correct |
26 |
Correct |
123 ms |
49340 KB |
Output is correct |
27 |
Correct |
154 ms |
49208 KB |
Output is correct |
28 |
Correct |
151 ms |
49500 KB |
Output is correct |
29 |
Correct |
182 ms |
50916 KB |
Output is correct |
30 |
Correct |
232 ms |
52548 KB |
Output is correct |
31 |
Correct |
125 ms |
49480 KB |
Output is correct |
32 |
Correct |
145 ms |
49300 KB |
Output is correct |
33 |
Correct |
151 ms |
49552 KB |
Output is correct |
34 |
Correct |
191 ms |
51560 KB |
Output is correct |
35 |
Correct |
200 ms |
54488 KB |
Output is correct |
36 |
Correct |
198 ms |
51428 KB |
Output is correct |