# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
778027 |
2023-07-10T03:27:20 Z |
mars4 |
Valley (BOI19_valley) |
C++17 |
|
173 ms |
33272 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 i128 __int128_t
#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 T> ostream& operator<<(ostream& out,ordered_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>>> g;
vector<ll> dist;
void dfs(ll cur,ll prev)
{
for(auto [nxt,w]:g[cur])
{
if(nxt!=prev)
{
dist[nxt]=dist[cur]+w;
dfs(nxt,cur);
}
}
}
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)
{
if(segtree[i+N]>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_down;
SegtreeMin s_up;
void init(vector<vector<ll>> &v,ll root=0)
{
N=(ll)v.size();
s_down.init(N,2*inf);
s_up.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 cur=node;
while(true)
{
s_down.update(st[cur],dist[node]);
s_up.update(st[cur],dist[node]-2*dist[cur]);
ll ncur=parent[tp[cur]];
if(cur==ncur)
{
break;
}
cur=ncur;
}
}
// use appropriate query operation (vertex/edge)
ll query(ll node,ll cut)
{
ll cur=node;
ll res=inf;
while(depth[tp[cur]]>depth[cut])
{
ll up_val=s_up.query(st[tp[cur]],st[cur])+dist[node];
ll down_val=s_down.query(st[cur],st[dn[tp[cur]]])+dist[node]-2*dist[cur];
res=min({res,up_val,down_val});
cur=parent[tp[cur]];
}
ll up_val=s_up.query(st[cut],st[cur])+dist[node];
ll down_val=s_down.query(st[cur],st[dn[tp[cur]]])+dist[node]-2*dist[cur];
res=min({res,up_val,down_val});
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--;
v=vector<vector<ll>>(n);
g=vector<vector<pair<ll,ll>>>(n);
dist=vector<ll>(n);
vector<pair<ll,ll>> edges(n-1);
forn(i,0,n-1)
{
cin>>l>>r>>d;
l--,r--;
v[l].push_back(r);
v[r].push_back(l);
g[l].push_back({r,d});
g[r].push_back({l,d});
edges[i]={l,r};
}
dfs(root,-1);
HLD hld;
hld.init(v,root);
forn(i,0,m)
{
cin>>d;
hld.update(d-1);
}
forn(i,0,q)
{
cin>>k>>d;
k--,d--;
auto [l,r]=edges[k];
if(hld.depth[l]<hld.depth[r])
{
swap(l,r);
}
if(hld.st[l]<=hld.st[d] and hld.ed[l]>=hld.st[d])
{
ll res=hld.query(d,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:227:5: warning: unused variable 'z' [-Wunused-variable]
227 | ll z,n,m,t,k,i,j,l,d,h,r;
| ^
valley.cpp:227:11: warning: unused variable 't' [-Wunused-variable]
227 | ll z,n,m,t,k,i,j,l,d,h,r;
| ^
valley.cpp:227:15: warning: unused variable 'i' [-Wunused-variable]
227 | ll z,n,m,t,k,i,j,l,d,h,r;
| ^
valley.cpp:227:17: warning: unused variable 'j' [-Wunused-variable]
227 | ll z,n,m,t,k,i,j,l,d,h,r;
| ^
valley.cpp:227:23: warning: unused variable 'h' [-Wunused-variable]
227 | ll z,n,m,t,k,i,j,l,d,h,r;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
456 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
456 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
588 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
584 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
596 KB |
Output is correct |
11 |
Correct |
2 ms |
596 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
1 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
149 ms |
29604 KB |
Output is correct |
2 |
Correct |
141 ms |
29260 KB |
Output is correct |
3 |
Correct |
152 ms |
29204 KB |
Output is correct |
4 |
Correct |
173 ms |
30924 KB |
Output is correct |
5 |
Correct |
144 ms |
31040 KB |
Output is correct |
6 |
Correct |
147 ms |
32828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
456 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
588 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
584 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
596 KB |
Output is correct |
11 |
Correct |
2 ms |
596 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
1 ms |
596 KB |
Output is correct |
15 |
Correct |
149 ms |
29604 KB |
Output is correct |
16 |
Correct |
141 ms |
29260 KB |
Output is correct |
17 |
Correct |
152 ms |
29204 KB |
Output is correct |
18 |
Correct |
173 ms |
30924 KB |
Output is correct |
19 |
Correct |
144 ms |
31040 KB |
Output is correct |
20 |
Correct |
147 ms |
32828 KB |
Output is correct |
21 |
Correct |
96 ms |
29208 KB |
Output is correct |
22 |
Correct |
107 ms |
28568 KB |
Output is correct |
23 |
Correct |
118 ms |
28636 KB |
Output is correct |
24 |
Correct |
121 ms |
30548 KB |
Output is correct |
25 |
Correct |
132 ms |
33272 KB |
Output is correct |
26 |
Correct |
103 ms |
29220 KB |
Output is correct |
27 |
Correct |
133 ms |
28604 KB |
Output is correct |
28 |
Correct |
126 ms |
28760 KB |
Output is correct |
29 |
Correct |
120 ms |
30060 KB |
Output is correct |
30 |
Correct |
120 ms |
31436 KB |
Output is correct |
31 |
Correct |
115 ms |
29260 KB |
Output is correct |
32 |
Correct |
125 ms |
28748 KB |
Output is correct |
33 |
Correct |
157 ms |
28872 KB |
Output is correct |
34 |
Correct |
129 ms |
30532 KB |
Output is correct |
35 |
Correct |
113 ms |
33116 KB |
Output is correct |
36 |
Correct |
160 ms |
30540 KB |
Output is correct |