Submission #501518

#TimeUsernameProblemLanguageResultExecution timeMemory
501518mars4Valley (BOI19_valley)C++17
9 / 100
216 ms29704 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...