# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
441451 |
2021-07-05T08:16:37 Z |
cpp219 |
Valley (BOI19_valley) |
C++14 |
|
281 ms |
53500 KB |
#pragma GCC optimization O2
#pragma GCC optimization "unroll-loop"
#pragma target ("avx2")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e5 + 9;
const ll Log2 = 20;
const ll inf = 1e18 + 7;
const ll lim = 1e16 + 7;
vector<LL> g[N];
LL edge[N];
ll n,S,Q,E,x,y,w,par[N][20],d[N],dp[N][20],val[N],dep[N];
ll nTime,L[N],R[N];
void DFS(ll u,ll p){
L[u] = R[u] = nTime; nTime++;
for (auto i : g[u]){
ll v = i.fs,L = i.sc;
if (v == p) continue;
d[v] = d[u] + 1; dep[v] = dep[u] + L; par[v][0] = u;
DFS(v,u); R[u] = max(R[u],R[v]);
val[u] = min(val[u],L + val[v]);
}
}
void reDFS(ll u,ll p){
//cout<<u<<" "<<p<<"\n";
//cout<<g[u][0].fs; exit(0);
for (ll i = 1;i < Log2;i++) if ((1 << i) <= d[u])
par[u][i] = par[par[u][i - 1]][i - 1],
dp[u][i] = min(dp[u][i - 1],dp[par[u][i - 1]][i - 1]);
for (auto i : g[u]) if (i.fs != p){
dp[i.fs][0] = val[u] - dep[u];
reDFS(i.fs,u);
}
}
ll Jump(ll node,ll step){
ll res = val[node] - dep[node];
for (ll i = Log2 - 1;i >= 0;i--){
if ((1 << i) > step) continue;
res = min(res,dp[node][i]); node = par[node][i];
step -= (1 << i);
}
//cout<<val[2] - dep[2]; exit(0);
return res;
}
int main(){
ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
#define task "test"
if (fopen(task".INP","r")){
freopen(task".INP","r",stdin);
freopen(task".OUT","w",stdout);
}
cin>>n>>S>>Q>>E; fill(val,val + n + 1,inf);
for (ll i = 1;i < n;i++){
cin>>x>>y>>w; edge[i] = {x,y};
g[x].push_back({y,w}); g[y].push_back({x,w});
}
for (ll i = 1;i <= S;i++) cin>>x,val[x] = 0;
DFS(E,0); reDFS(E,0); //cout<<dp[4][0]; return 0;
while(Q--){
cin>>x>>y;
if (d[edge[x].fs] < d[edge[x].sc]) swap(edge[x].fs,edge[x].sc);
ll l = edge[x].fs;
if (L[l] <= L[y] && R[y] <= R[l]){
ll kq = Jump(y,d[y] - d[l]); //cout<<kq; return 0;
if (kq > lim) cout<<"oo";
else cout<<kq + dep[y];
}
else cout<<"escaped";
cout<<"\n";
}
}
Compilation message
valley.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
1 | #pragma GCC optimization O2
|
valley.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
2 | #pragma GCC optimization "unroll-loop"
|
valley.cpp:3: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
3 | #pragma target ("avx2")
|
valley.cpp: In function 'int main()':
valley.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | freopen(task".INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | freopen(task".OUT","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
2764 KB |
Output is correct |
2 |
Correct |
5 ms |
2892 KB |
Output is correct |
3 |
Correct |
13 ms |
2812 KB |
Output is correct |
4 |
Correct |
4 ms |
2764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
2764 KB |
Output is correct |
2 |
Correct |
5 ms |
2892 KB |
Output is correct |
3 |
Correct |
13 ms |
2812 KB |
Output is correct |
4 |
Correct |
4 ms |
2764 KB |
Output is correct |
5 |
Correct |
3 ms |
3132 KB |
Output is correct |
6 |
Correct |
3 ms |
3148 KB |
Output is correct |
7 |
Correct |
3 ms |
3148 KB |
Output is correct |
8 |
Correct |
3 ms |
3148 KB |
Output is correct |
9 |
Correct |
3 ms |
3148 KB |
Output is correct |
10 |
Correct |
3 ms |
3148 KB |
Output is correct |
11 |
Correct |
3 ms |
3148 KB |
Output is correct |
12 |
Correct |
3 ms |
3148 KB |
Output is correct |
13 |
Correct |
3 ms |
3084 KB |
Output is correct |
14 |
Correct |
3 ms |
3148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
178 ms |
45124 KB |
Output is correct |
2 |
Correct |
217 ms |
48072 KB |
Output is correct |
3 |
Correct |
216 ms |
48296 KB |
Output is correct |
4 |
Correct |
243 ms |
50244 KB |
Output is correct |
5 |
Correct |
241 ms |
50356 KB |
Output is correct |
6 |
Correct |
276 ms |
52476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
2764 KB |
Output is correct |
2 |
Correct |
5 ms |
2892 KB |
Output is correct |
3 |
Correct |
13 ms |
2812 KB |
Output is correct |
4 |
Correct |
4 ms |
2764 KB |
Output is correct |
5 |
Correct |
3 ms |
3132 KB |
Output is correct |
6 |
Correct |
3 ms |
3148 KB |
Output is correct |
7 |
Correct |
3 ms |
3148 KB |
Output is correct |
8 |
Correct |
3 ms |
3148 KB |
Output is correct |
9 |
Correct |
3 ms |
3148 KB |
Output is correct |
10 |
Correct |
3 ms |
3148 KB |
Output is correct |
11 |
Correct |
3 ms |
3148 KB |
Output is correct |
12 |
Correct |
3 ms |
3148 KB |
Output is correct |
13 |
Correct |
3 ms |
3084 KB |
Output is correct |
14 |
Correct |
3 ms |
3148 KB |
Output is correct |
15 |
Correct |
178 ms |
45124 KB |
Output is correct |
16 |
Correct |
217 ms |
48072 KB |
Output is correct |
17 |
Correct |
216 ms |
48296 KB |
Output is correct |
18 |
Correct |
243 ms |
50244 KB |
Output is correct |
19 |
Correct |
241 ms |
50356 KB |
Output is correct |
20 |
Correct |
276 ms |
52476 KB |
Output is correct |
21 |
Correct |
188 ms |
48388 KB |
Output is correct |
22 |
Correct |
198 ms |
48216 KB |
Output is correct |
23 |
Correct |
230 ms |
48484 KB |
Output is correct |
24 |
Correct |
240 ms |
50428 KB |
Output is correct |
25 |
Correct |
244 ms |
53500 KB |
Output is correct |
26 |
Correct |
162 ms |
48288 KB |
Output is correct |
27 |
Correct |
180 ms |
48176 KB |
Output is correct |
28 |
Correct |
225 ms |
48384 KB |
Output is correct |
29 |
Correct |
258 ms |
49832 KB |
Output is correct |
30 |
Correct |
280 ms |
51624 KB |
Output is correct |
31 |
Correct |
192 ms |
48344 KB |
Output is correct |
32 |
Correct |
197 ms |
48140 KB |
Output is correct |
33 |
Correct |
219 ms |
48444 KB |
Output is correct |
34 |
Correct |
281 ms |
50496 KB |
Output is correct |
35 |
Correct |
245 ms |
53232 KB |
Output is correct |
36 |
Correct |
232 ms |
50640 KB |
Output is correct |