# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
699838 |
2023-02-18T06:02:09 Z |
Iliya_ |
Valley (BOI19_valley) |
C++14 |
|
267 ms |
55756 KB |
// IN THE NAME OF GOD
#include<bits/stdc++.h>
//#pragma GCC optimize ("O2,unroll-loops,O3,Ofast,no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#define endl '\n'
#define file_reading freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
using namespace std;
typedef long long ll;
typedef long double dll;
typedef unsigned long long ull;
const ll B = 1e5+7, logg = 23, inf = 1e18;
ll dist[B],sub[B],par[logg][B],sp[logg][B],h[B],mark[B],e[B][2];
vector<pair<int,int>> g[B];
void dfs(int v, int father){
mark[v] = 1;
par[0][v] = father;
for(int i=1; i<logg; i++){par[i][v] = par[i-1][par[i-1][v]];}
for(pair<int,int> cur : g[v]){
int u = cur.first, w = cur.second;
if (mark[u]){continue;}
dist[u] = dist[v] + w;
h[u] = h[v] + 1;
dfs(u,v);
sub[v] = min(sub[v],sub[u]+w);
}
sp[0][v] = sub[v]-dist[v];
}
pair<ll,ll> k_par(int v, ll k){
if (k < 0){return{inf,inf};}
ll ans = inf;
for(int i=logg-1; i>=0; i--){
if ((k>>i)&1){
ans = min(ans,sp[i][v]);
v = par[i][v];
}
}
if (sp[0][v] < ans){ans = sp[0][v];}
return {v,ans};
}
void solve(){
int n,s,q,st; cin >> n >> s >> q >> st;
sub[1] = inf;
for(int i=1; i<n; i++){
int v,u,w; cin >> v >> u >> w;
g[v].push_back({u,w});
g[u].push_back({v,w});
e[i][0] = v; e[i][1] = u;
sub[i+1] = inf;
}
for(int i=1; i<=s; i++){
int get; cin >> get;
sub[get] = 0;
}
dfs(st,0);
for(int k = 1; k < logg; k++){
for (int i = 1; i<=n; i++){
sp[k][i] = min(sp[k-1][i],sp[k-1][par[k-1][i]]);
}
}
while(q--){
int v,rem; cin >> rem >> v;
if (h[e[rem][0]] < h[e[rem][1]]){swap(e[rem][0],e[rem][1]);}
pair<ll,ll> giv = k_par(v,h[v]-h[e[rem][0]]);
if (giv.first != e[rem][0]){
cout << "escaped" << endl;
continue;
}
ll tmp = giv.second + dist[v];
if (tmp >= inf){cout << "oo" << endl;}
else{cout << tmp << endl;}
}
}
int32_t main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t; t=1;
while(t--){solve();}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3060 KB |
Output is correct |
2 |
Correct |
4 ms |
3064 KB |
Output is correct |
3 |
Correct |
4 ms |
3028 KB |
Output is correct |
4 |
Correct |
4 ms |
3028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3060 KB |
Output is correct |
2 |
Correct |
4 ms |
3064 KB |
Output is correct |
3 |
Correct |
4 ms |
3028 KB |
Output is correct |
4 |
Correct |
4 ms |
3028 KB |
Output is correct |
5 |
Correct |
3 ms |
3388 KB |
Output is correct |
6 |
Correct |
3 ms |
3412 KB |
Output is correct |
7 |
Correct |
3 ms |
3324 KB |
Output is correct |
8 |
Correct |
3 ms |
3336 KB |
Output is correct |
9 |
Correct |
3 ms |
3328 KB |
Output is correct |
10 |
Correct |
3 ms |
3412 KB |
Output is correct |
11 |
Correct |
3 ms |
3400 KB |
Output is correct |
12 |
Correct |
3 ms |
3412 KB |
Output is correct |
13 |
Correct |
3 ms |
3412 KB |
Output is correct |
14 |
Correct |
3 ms |
3412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
143 ms |
51724 KB |
Output is correct |
2 |
Correct |
148 ms |
51368 KB |
Output is correct |
3 |
Correct |
170 ms |
51404 KB |
Output is correct |
4 |
Correct |
188 ms |
53040 KB |
Output is correct |
5 |
Correct |
215 ms |
53204 KB |
Output is correct |
6 |
Correct |
251 ms |
55208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3060 KB |
Output is correct |
2 |
Correct |
4 ms |
3064 KB |
Output is correct |
3 |
Correct |
4 ms |
3028 KB |
Output is correct |
4 |
Correct |
4 ms |
3028 KB |
Output is correct |
5 |
Correct |
3 ms |
3388 KB |
Output is correct |
6 |
Correct |
3 ms |
3412 KB |
Output is correct |
7 |
Correct |
3 ms |
3324 KB |
Output is correct |
8 |
Correct |
3 ms |
3336 KB |
Output is correct |
9 |
Correct |
3 ms |
3328 KB |
Output is correct |
10 |
Correct |
3 ms |
3412 KB |
Output is correct |
11 |
Correct |
3 ms |
3400 KB |
Output is correct |
12 |
Correct |
3 ms |
3412 KB |
Output is correct |
13 |
Correct |
3 ms |
3412 KB |
Output is correct |
14 |
Correct |
3 ms |
3412 KB |
Output is correct |
15 |
Correct |
143 ms |
51724 KB |
Output is correct |
16 |
Correct |
148 ms |
51368 KB |
Output is correct |
17 |
Correct |
170 ms |
51404 KB |
Output is correct |
18 |
Correct |
188 ms |
53040 KB |
Output is correct |
19 |
Correct |
215 ms |
53204 KB |
Output is correct |
20 |
Correct |
251 ms |
55208 KB |
Output is correct |
21 |
Correct |
134 ms |
51240 KB |
Output is correct |
22 |
Correct |
154 ms |
50936 KB |
Output is correct |
23 |
Correct |
142 ms |
50756 KB |
Output is correct |
24 |
Correct |
186 ms |
52800 KB |
Output is correct |
25 |
Correct |
267 ms |
55756 KB |
Output is correct |
26 |
Correct |
135 ms |
51316 KB |
Output is correct |
27 |
Correct |
155 ms |
50904 KB |
Output is correct |
28 |
Correct |
141 ms |
50812 KB |
Output is correct |
29 |
Correct |
183 ms |
52228 KB |
Output is correct |
30 |
Correct |
229 ms |
53628 KB |
Output is correct |
31 |
Correct |
141 ms |
51396 KB |
Output is correct |
32 |
Correct |
180 ms |
51028 KB |
Output is correct |
33 |
Correct |
145 ms |
50984 KB |
Output is correct |
34 |
Correct |
178 ms |
52720 KB |
Output is correct |
35 |
Correct |
230 ms |
55640 KB |
Output is correct |
36 |
Correct |
174 ms |
52920 KB |
Output is correct |