| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 501518 |
2022-01-03T18:32:01 Z |
mars4 |
Valley (BOI19_valley) |
C++17 |
|
216 ms |
29704 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ff first
#define ss second
#define ll int64_t
#define ld long double
#define nl cout<<"\n"
#define all(v) v.begin(),v.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define forn(i,a,b) for(int64_t i=int64_t(a);i<int64_t(b);++i)
#define forb(i,a,b) for(int64_t i=int64_t(a);i>=int64_t(b);--i)
#define fastio() ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mod 1'000'000'007
#define mod2 998'244'353
#define inf 1'000'000'000'000'007
#define pi 3.14159265358979323846
template<class key,class cmp=std::less<key>>
using ordered_set=tree<key,null_type,cmp,rb_tree_tag,tree_order_statistics_node_update>;
template<class L,class R> ostream& operator<<(ostream& out,pair<L,R> &p) {return out<<"("<<p.ff<<", "<<p.ss<<")";}
template<class T> ostream& operator<<(ostream& out,vector<T> &v) {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";}
template<class T> ostream& operator<<(ostream& out,deque<T> &v) {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";}
template<class T> ostream& operator<<(ostream& out,set<T> &s) {out<<"{";for(auto it=s.begin();it!=s.end();++it){if(it!=s.begin())out<<", ";out<<*it;}return out<<"}";}
template<class L,class R> ostream& operator<<(ostream& out,map<L,R> &m) {out<<"{";for(auto it=m.begin();it!=m.end();++it){if(it!=m.begin())out<<", ";out<<*it;}return out<<"}";}
void dbg_out() {cerr<<"]\n";}
template<typename Head,typename... Tail>
void dbg_out(Head H,Tail... T) {cerr<<H;if(sizeof...(Tail))cerr<<", ";dbg_out(T...);}
#ifdef LOCAL
#define dbg(...) cerr<<"["<<#__VA_ARGS__<<"] = [",dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
//---------------------------------mars4---------------------------------
vector<vector<ll>> v;
vector<vector<pair<ll,ll>>> ve;
vector<ll> len;
void dfs(ll cur,ll prev,ll d)
{
len[cur]=d;
for(auto [i,w]:ve[cur])
{
if(i!=prev)
{
dfs(i,cur,d+w);
}
}
}
class SegtreeMin
{
ll N;
public:
vector<ll> segtree;
void init(ll n,ll val=0)
{
N=n;
segtree=vector<ll>(N<<1,val);
}
void build(vector<ll> &a)
{
forn(i,0,N)
segtree[i+N]=a[i];
forb(i,N-1,1)
segtree[i]=min(segtree[i<<1],segtree[i<<1|1]);
}
void update(ll i,ll val)
{
for(segtree[i+=N]=val;i>>=1;)
segtree[i]=min(segtree[i<<1],segtree[i<<1|1]);
}
ll query(ll l,ll r)
{
ll res=2*inf;
for(l+=N,r+=N+1;l<r;l>>=1,r>>=1)
{
if(l&1) res=min(res,segtree[l++]);
if(r&1) res=min(res,segtree[--r]);
}
return res;
}
};
class HLD
{
ll N;
ll timer;
void dfs_sz(ll cur,ll prev,vector<vector<ll>> &v)
{
child[cur]=1;
parent[cur]=prev;
for(ll i:v[cur])
{
if(i!=prev)
{
depth[i]=depth[cur]+1;
dfs_sz(i,cur,v);
child[cur]+=child[i];
}
}
}
void dfs_hld(ll cur,ll prev,ll top,vector<vector<ll>> &v)
{
timer++;
st[cur]=timer;
tp[cur]=top;
dn[top]=cur;
ll h_ind=-1,h_sz=-1;
for(ll i=0;i<(ll)v[cur].size();i++)
{
if(v[cur][i]!=prev)
{
if(child[v[cur][i]]>h_sz)
{
h_ind=i;
h_sz=child[v[cur][i]];
}
}
}
if(h_ind==-1)
{
ed[cur]=timer;
return;
}
swap(v[cur][0],v[cur][h_ind]);
dfs_hld(v[cur][0],cur,top,v);
for(ll i:v[cur])
{
if(i!=prev and i!=v[cur][0])
{
dfs_hld(i,cur,i,v);
}
}
ed[cur]=timer;
}
public:
vector<ll> child;
vector<ll> parent;
vector<ll> depth;
vector<ll> st;
vector<ll> ed;
vector<ll> tp;
vector<ll> dn;
// use segtree class
SegtreeMin s_up,s_down;
void init(vector<vector<ll>> &v,ll root=0)
{
N=(ll)v.size();
s_up.init(N,2*inf);
s_down.init(N,2*inf);
child=vector<ll>(N);
parent=vector<ll>(N);
depth=vector<ll>(N);
st=vector<ll>(N);
ed=vector<ll>(N);
tp=vector<ll>(N);
dn=vector<ll>(N);
timer=-1;
dfs_sz(root,root,v);
dfs_hld(root,root,root,v);
}
void update(ll node)
{
ll dist=0;
while(true)
{
s_up.update(st[node],dist-len[node]);
s_down.update(st[node],dist+len[node]);
ll new_node=parent[tp[node]];
if(new_node==node)
{
break;
}
dist+=len[node]-len[new_node];
node=new_node;
}
}
// use appropriate query operation (vertex/edge)
ll query(ll node,ll cut)
{
ll res=2*inf;
ll dist=0;
while(depth[tp[node]]>=depth[cut])
{
ll up_val=s_up.query(st[tp[node]],st[node]);
ll down_val=s_down.query(st[node],st[dn[tp[node]]]);
ll nres=min(up_val+len[node],down_val-len[node])+dist;
res=min(res,nres);
ll new_node=parent[tp[node]];
if(new_node==node)
{
break;
}
dist+=len[node]-len[new_node];
node=new_node;
}
if(depth[node]>=depth[cut])
{
ll up_val=s_up.query(st[cut],st[node]);
ll down_val=s_down.query(st[node],st[dn[tp[node]]]);
ll nres=min(up_val+len[node],down_val-len[node])+dist;
res=min(res,nres);
}
return res;
}
};
int main()
{
fastio();
ll z,n,m,t,k,i,j,l,d,h,r;
ll q,root;
cin>>n>>m>>q>>root;
root--;
ve=vector<vector<pair<ll,ll>>>(n);
v=vector<vector<ll>>(n);
len=vector<ll>(n);
vector<pair<ll,ll>> edges(n-1);
forn(i,0,n-1)
{
cin>>l>>r>>d;
l--,r--;
ve[l].push_back({r,d});
ve[r].push_back({l,d});
v[l].push_back(r);
v[r].push_back(l);
edges[i]={l,r};
}
dfs(root,-1,0);
HLD hld;
hld.init(v,root);
forn(i,0,m)
{
cin>>r;
r--;
hld.update(r);
}
while(q--)
{
ll ind,cur;
cin>>ind>>cur;
ind--,cur--;
auto [l,r]=edges[ind];
if(hld.depth[l]<hld.depth[r])
{
swap(l,r);
}
if(hld.st[l]<=hld.st[cur] and hld.ed[l]>=hld.ed[cur])
{
ll res=hld.query(cur,l);
if(res>=inf)
{
cout<<"oo\n";
}
else
{
cout<<res<<"\n";
}
}
else
{
cout<<"escaped\n";
}
}
cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
return 0;
}
Compilation message
valley.cpp: In function 'int main()':
valley.cpp:233:5: warning: unused variable 'z' [-Wunused-variable]
233 | ll z,n,m,t,k,i,j,l,d,h,r;
| ^
valley.cpp:233:11: warning: unused variable 't' [-Wunused-variable]
233 | ll z,n,m,t,k,i,j,l,d,h,r;
| ^
valley.cpp:233:13: warning: unused variable 'k' [-Wunused-variable]
233 | ll z,n,m,t,k,i,j,l,d,h,r;
| ^
valley.cpp:233:15: warning: unused variable 'i' [-Wunused-variable]
233 | ll z,n,m,t,k,i,j,l,d,h,r;
| ^
valley.cpp:233:17: warning: unused variable 'j' [-Wunused-variable]
233 | ll z,n,m,t,k,i,j,l,d,h,r;
| ^
valley.cpp:233:23: warning: unused variable 'h' [-Wunused-variable]
233 | ll z,n,m,t,k,i,j,l,d,h,r;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
460 KB |
Output is correct |
| 2 |
Correct |
2 ms |
452 KB |
Output is correct |
| 3 |
Correct |
2 ms |
460 KB |
Output is correct |
| 4 |
Correct |
2 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
460 KB |
Output is correct |
| 2 |
Correct |
2 ms |
452 KB |
Output is correct |
| 3 |
Correct |
2 ms |
460 KB |
Output is correct |
| 4 |
Correct |
2 ms |
460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
588 KB |
Output is correct |
| 6 |
Correct |
1 ms |
588 KB |
Output is correct |
| 7 |
Correct |
1 ms |
588 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
584 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
216 ms |
29704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
460 KB |
Output is correct |
| 2 |
Correct |
2 ms |
452 KB |
Output is correct |
| 3 |
Correct |
2 ms |
460 KB |
Output is correct |
| 4 |
Correct |
2 ms |
460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
588 KB |
Output is correct |
| 6 |
Correct |
1 ms |
588 KB |
Output is correct |
| 7 |
Correct |
1 ms |
588 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
584 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
