oj.uz

Submission #501641

# Submission time Handle Problem Language Result Execution time Memory
501641 2022-01-04T09:06:39 Z mars4 Valley (BOI19_valley) C++17
100 / 100
 300 ms 59372 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<pair<ll,ll>>> v;
vector<ll> st;
vector<ll> ed;
vector<ll> sval;
vector<ll> dist;
vector<ll> depth;
vector<bool> shop;
vector<vector<ll>> dp;
vector<vector<ll>> val;
ll timer;
ll logN=18;

void dfs(ll cur,ll prev,ll len,ll level)
{
	timer++;
	st[cur]=timer;
	dist[cur]=len;
	depth[cur]=level;
	sval[cur]=shop[cur]?dist[cur]:inf;
	for(auto [i,w]:v[cur])
	{
		if(i!=prev)
		{
			dfs(i,cur,len+w,level+1);
			sval[cur]=min(sval[cur],sval[i]);
		}
	}
	dp[cur][0]=prev;
	val[cur][0]=sval[cur]==inf?inf:sval[cur]-2*dist[cur];
	ed[cur]=timer;
}

int main()
{
	fastio();
	ll z,n,m,t,k,i,j,l,d,h,r;
	ll s,root;
	cin>>n>>s>>m>>root;
	root--;
	v=vector<vector<pair<ll,ll>>>(n);
	dp=vector<vector<ll>>(n,vector<ll>(logN));
	val=vector<vector<ll>>(n,vector<ll>(logN));
	st=vector<ll>(n);
	ed=vector<ll>(n);
	sval=vector<ll>(n);
	dist=vector<ll>(n);
	depth=vector<ll>(n);
	shop=vector<bool>(n);
	timer=-1;
	vector<pair<ll,ll>> edges(n-1);
	forn(i,0,n-1)
	{
		cin>>l>>r>>d;
		l--,r--;
		v[l].push_back({r,d});
		v[r].push_back({l,d});
		edges[i]={l,r};
	}
	forn(i,0,s)
	{
		cin>>r;
		shop[r-1]=true;
	}
	dfs(root,root,0,0);
	forn(j,1,logN)
	{
		forn(i,0,n)
		{
			dp[i][j]=dp[dp[i][j-1]][j-1];
			val[i][j]=min(val[i][j-1],val[dp[i][j-1]][j-1]);
		}
	}
	while(m--)
	{
		ll ind,cur;
		cin>>ind>>cur;
		ind--,cur--;
		auto [l,r]=edges[ind];
		if(dist[l]<dist[r])
		{
			swap(l,r);
		}
		if(st[l]<=st[cur] and ed[l]>=ed[cur])
		{
			ll mval=val[l][0];
			ll diff=depth[cur]-depth[l];
			ll icur=cur;
			forb(k,logN-1,0)
			{
				if(diff&(1ll<<k))
				{
					mval=min(mval,val[cur][k]);
					cur=dp[cur][k];
				}
			}
			mval+=dist[icur];
			if(mval>=inf)
			{
				cout<<"oo\n";
			}
			else
			{
				cout<<mval<<"\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:79:5: warning: unused variable 'z' [-Wunused-variable]
   79 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |     ^
valley.cpp:79:11: warning: unused variable 't' [-Wunused-variable]
   79 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |           ^
valley.cpp:79:13: warning: unused variable 'k' [-Wunused-variable]
   79 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |             ^
valley.cpp:79:15: warning: unused variable 'i' [-Wunused-variable]
   79 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |               ^
valley.cpp:79:17: warning: unused variable 'j' [-Wunused-variable]
   79 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |                 ^
valley.cpp:79:23: warning: unused variable 'h' [-Wunused-variable]
   79 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |                       ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 444 KB Output is correct
3 Correct 4 ms 452 KB Output is correct
4 Correct 2 ms 460 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 444 KB Output is correct
3 Correct 4 ms 452 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 2 ms 844 KB Output is correct
11 Correct 2 ms 844 KB Output is correct
12 Correct 1 ms 844 KB Output is correct
13 Correct 2 ms 844 KB Output is correct
14 Correct 1 ms 812 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 49988 KB Output is correct
2 Correct 213 ms 49736 KB Output is correct
3 Correct 225 ms 49916 KB Output is correct
4 Correct 273 ms 52288 KB Output is correct
5 Correct 214 ms 52256 KB Output is correct
6 Correct 267 ms 54944 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 444 KB Output is correct
3 Correct 4 ms 452 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 2 ms 844 KB Output is correct
11 Correct 2 ms 844 KB Output is correct
12 Correct 1 ms 844 KB Output is correct
13 Correct 2 ms 844 KB Output is correct
14 Correct 1 ms 812 KB Output is correct
15 Correct 195 ms 49988 KB Output is correct
16 Correct 213 ms 49736 KB Output is correct
17 Correct 225 ms 49916 KB Output is correct
18 Correct 273 ms 52288 KB Output is correct
19 Correct 214 ms 52256 KB Output is correct
20 Correct 267 ms 54944 KB Output is correct
21 Correct 187 ms 53240 KB Output is correct
22 Correct 192 ms 53044 KB Output is correct
23 Correct 214 ms 53408 KB Output is correct
24 Correct 253 ms 55816 KB Output is correct
25 Correct 262 ms 59372 KB Output is correct
26 Correct 180 ms 53272 KB Output is correct
27 Correct 217 ms 53028 KB Output is correct
28 Correct 221 ms 53308 KB Output is correct
29 Correct 256 ms 55016 KB Output is correct
30 Correct 300 ms 56888 KB Output is correct
31 Correct 208 ms 53356 KB Output is correct
32 Correct 233 ms 53164 KB Output is correct
33 Correct 255 ms 53404 KB Output is correct
34 Correct 289 ms 55644 KB Output is correct
35 Correct 297 ms 59168 KB Output is correct
36 Correct 282 ms 55672 KB Output is correct