# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
380907 |
2021-03-23T14:26:49 Z |
leaked |
Valley (BOI19_valley) |
C++14 |
|
500 ms |
36576 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx,avx2,tune=native")
#define m_p make_pair
#define f first
#define s second
#define vec vector
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pw(x) (1LL<<x)
#define pb push_back
#define sz(x) (int)x.size()
#define endl '\n'
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define print(x) cerr<<"[ "<<(#x)<<": "<<x<<" ]"<<endl;cout.flush();
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
template<class T> using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T> bool umin(T &a,const T b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T b){return (a<b?a=b,1:0);}
const int N=1e5+1;
const ll inf=1e17;
int up[N][20];
int in[N],out[N],e,n,m,q,tt=-1;
bool painted[N];
vec<pii>edges;
ll p[4*N];
ll t[4*N];
vec<pii>g[N];
ll ans[N];
vec<array<int,3>>qry[N];
void push(int v,int tl,int tr){
if(tl==tr || !p[v]){
return;
}
p[2*v]+=p[v];
p[2*v+1]+=p[v];
t[2*v]+=p[v];
t[2*v+1]+=p[v];
p[v]=0;
}
void upd(int l,int r,ll x,int v,int tl,int tr){
if(tl>=l && tr<=r){
p[v]+=x;
t[v]+=x;
return;
}
if(tl>r || tr<l) return;
int tm=(tl+tr)>>1;
push(v,tl,tr);
upd(l,r,x,2*v,tl,tm);
upd(l,r,x,2*v+1,tm+1,tr);
t[v]=min(t[2*v],t[2*v+1]);
}
void dfs1(int v,ll d,int p){
in[v]=++tt;
if(painted[v]){
upd(in[v],in[v],-inf,1,0,n-1);
upd(in[v],in[v],d,1,0,n-1);
}
up[v][0]=p;
for(int i=1;i<20;i++) up[v][i]=up[up[v][i-1]][i-1];
for(auto &z : g[v]){
if(z.f==p) continue;
dfs1(z.f,d+z.s,v);
}
out[v]=tt;
}
bool is(int a,int b){
return in[a]<=in[b]&&out[a]>=out[b];
}
int lca(int a,int b){
if(is(a,b)) return a;
if(is(b,a)) return b;
for(int i=19;i>=0;i--){
if(!is(up[a][i],b)) a=up[a][i];
}
return up[a][0];
}
void dfs2(int v,int p){
int lc=lca(v,e);
for(auto &z : qry[v]){
int a=z[1],b=z[2];
int i=z[0];
if(is(b,a)) swap(a,b);
// print(is(lc,a));print(z[0]);print(z[1]);print(z[2]);
if((is(lc,a) && is(b,v)) || (is(lc,a) && is(b,e))){
if(is(b,v)){
upd(0,n-1,inf,1,0,n-1);
upd(in[b],out[b],-inf,1,0,n-1);
ans[i]=t[1];
upd(0,n-1,-inf,1,0,n-1);
upd(in[b],out[b],inf,1,0,n-1);
}
else{
upd(in[b],out[b],inf,1,0,n-1);
ans[i]=t[1];
upd(in[b],out[b],-inf,1,0,n-1);
}
}
else{
ans[i]=-inf;
}
}
for(auto &z : g[v]){
if(z.f==p) continue;
upd(0,n-1,z.s,1,0,n-1);
upd(in[z.f],out[z.f],-2*z.s,1,0,n-1);
dfs2(z.f,v);
upd(0,n-1,-z.s,1,0,n-1);
upd(in[z.f],out[z.f],2*z.s,1,0,n-1);
}
}
signed main(){
fast_ioi;
cin>>n>>m>>q>>e;
--e;
for(int i=1;i<n;i++){
int v,u,w;
cin>>v>>u>>w;--v;--u;
g[v].pb({u,w});
g[u].pb({v,w});
edges.pb({v,u});
}
upd(0,n-1,inf,1,0,n-1);
for(int i=0;i<m;i++){
int x;
cin>>x;--x;
painted[x]=1;
}
for(int i=0;i<q;i++){
int a,b;
cin>>a>>b;--a;--b;
qry[b].pb({i,edges[a].f,edges[a].s});
// print(edges[a].f);
// print(edges[a].s);
// print(b);
}
dfs1(0,0,0);
dfs2(0,0);
for(int i=0;i<q;i++){
if(ans[i]>=inf/10*9){
cout<<"oo";
}
else if(ans[i]==-inf){
cout<<"escaped";
}
else{
cout<<ans[i];
}
cout<<endl;
}
return 0;
}
/*
5 2 1 1
1 2 3
1 3 2
3 4 1
3 5 2
2
4
4 5
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5484 KB |
Output is correct |
2 |
Correct |
9 ms |
5484 KB |
Output is correct |
3 |
Correct |
7 ms |
5484 KB |
Output is correct |
4 |
Correct |
7 ms |
5484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5484 KB |
Output is correct |
2 |
Correct |
9 ms |
5484 KB |
Output is correct |
3 |
Correct |
7 ms |
5484 KB |
Output is correct |
4 |
Correct |
7 ms |
5484 KB |
Output is correct |
5 |
Correct |
5 ms |
5356 KB |
Output is correct |
6 |
Correct |
5 ms |
5356 KB |
Output is correct |
7 |
Correct |
6 ms |
5356 KB |
Output is correct |
8 |
Correct |
6 ms |
5356 KB |
Output is correct |
9 |
Correct |
6 ms |
5380 KB |
Output is correct |
10 |
Correct |
6 ms |
5356 KB |
Output is correct |
11 |
Correct |
6 ms |
5356 KB |
Output is correct |
12 |
Correct |
6 ms |
5356 KB |
Output is correct |
13 |
Correct |
6 ms |
5356 KB |
Output is correct |
14 |
Correct |
6 ms |
5356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
391 ms |
30176 KB |
Output is correct |
2 |
Correct |
413 ms |
29920 KB |
Output is correct |
3 |
Correct |
446 ms |
29664 KB |
Output is correct |
4 |
Correct |
499 ms |
31900 KB |
Output is correct |
5 |
Correct |
410 ms |
31584 KB |
Output is correct |
6 |
Correct |
500 ms |
36576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5484 KB |
Output is correct |
2 |
Correct |
9 ms |
5484 KB |
Output is correct |
3 |
Correct |
7 ms |
5484 KB |
Output is correct |
4 |
Correct |
7 ms |
5484 KB |
Output is correct |
5 |
Correct |
5 ms |
5356 KB |
Output is correct |
6 |
Correct |
5 ms |
5356 KB |
Output is correct |
7 |
Correct |
6 ms |
5356 KB |
Output is correct |
8 |
Correct |
6 ms |
5356 KB |
Output is correct |
9 |
Correct |
6 ms |
5380 KB |
Output is correct |
10 |
Correct |
6 ms |
5356 KB |
Output is correct |
11 |
Correct |
6 ms |
5356 KB |
Output is correct |
12 |
Correct |
6 ms |
5356 KB |
Output is correct |
13 |
Correct |
6 ms |
5356 KB |
Output is correct |
14 |
Correct |
6 ms |
5356 KB |
Output is correct |
15 |
Correct |
391 ms |
30176 KB |
Output is correct |
16 |
Correct |
413 ms |
29920 KB |
Output is correct |
17 |
Correct |
446 ms |
29664 KB |
Output is correct |
18 |
Correct |
499 ms |
31900 KB |
Output is correct |
19 |
Correct |
410 ms |
31584 KB |
Output is correct |
20 |
Correct |
500 ms |
36576 KB |
Output is correct |
21 |
Correct |
318 ms |
29512 KB |
Output is correct |
22 |
Correct |
351 ms |
29204 KB |
Output is correct |
23 |
Correct |
376 ms |
29160 KB |
Output is correct |
24 |
Correct |
396 ms |
30688 KB |
Output is correct |
25 |
Correct |
407 ms |
34728 KB |
Output is correct |
26 |
Correct |
317 ms |
29536 KB |
Output is correct |
27 |
Correct |
343 ms |
29280 KB |
Output is correct |
28 |
Correct |
352 ms |
29152 KB |
Output is correct |
29 |
Correct |
396 ms |
31236 KB |
Output is correct |
30 |
Correct |
419 ms |
33376 KB |
Output is correct |
31 |
Correct |
318 ms |
29664 KB |
Output is correct |
32 |
Correct |
386 ms |
29304 KB |
Output is correct |
33 |
Correct |
360 ms |
29280 KB |
Output is correct |
34 |
Correct |
426 ms |
30816 KB |
Output is correct |
35 |
Correct |
381 ms |
34016 KB |
Output is correct |
36 |
Correct |
376 ms |
31328 KB |
Output is correct |