Submission #640097

#	Time	Username	Problem	Language	Result	Execution time	Memory
640097		StefanSebez	Valley (BOI19_valley)	C++14	0 / 100	308 ms	29884 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5+50;
const ll inf=1e18+50;
bool store[N];
bool escaped[N];
ll U[N],V[N],W[N];
ll depth[N],ct=0;
ll dp[N];
ll parent[N];
vector<pair<ll,ll>>E[N];
vector<pair<ll,ll>>query[N];
vector<ll>nodes;
ll res[N];
ll pref[N];
void DFSsetup(ll u)
{
	if(store[u]==true)
	{
		dp[u]=0;
	}
	ct++;
	depth[u]=ct;
	pref[u]+=pref[parent[u]];
	for(auto i:E[u])
	{
		if(i.first!=parent[u])
		{
			parent[i.first]=u;
			pref[i.first]+=i.second;
			DFSsetup(i.first);
			dp[u]=min(dp[u],dp[i.first]+i.second);
		}
	}
	ct--;
}
void DFSexit(ll u)
{
	nodes.push_back(u);
	for(ll i=0;i<query[u].size();i++)
	{
		ll x=U[query[u][i].first];
		ll y=V[query[u][i].first];
		if(x!=nodes[depth[x]-1] || y!=nodes[depth[y]-1])
		{
			escaped[query[u][i].second]=true;
		}
	}
	for(auto i:E[u])
	{
		if(i.first!=parent[u])
		{
			DFSexit(i.first);
		}
	}
	nodes.pop_back();
}
ll a[N],sum[N];
ll lc[2*N],rc[2*N],nc,root;
ll n;
void Build(ll &c,ll ss,ll se)
{
	nc++;
	c=nc;
	if(ss==se)
	{
		sum[c]=0;
		return;
	}
	ll mid=(ss+se)/2;
	Build(lc[c],ss,mid);
	Build(rc[c],mid+1,se);
	sum[c]=min(sum[lc[c]],sum[rc[c]]);
}
ll Get(ll c,ll ss,ll se,ll qs,ll qe)
{
	if(qs<=ss && se<=qe)
	{
		return sum[c];
	}
	if(qe<ss || se<qs)
	{
		return inf;
	}
	ll mid=(ss+se)/2;
	return min(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
}
void Update(ll c,ll ss,ll se,ll qind,ll qval)
{
	if(ss==se)
	{
		a[ss]=qval;
		sum[c]=qval;
		//printf("%i %i: %i\n",ss,se,sum[c]);
		return;
	}
	ll mid=(ss+se)/2;
	if(ss<=qind && qind<=mid)
	{
		Update(lc[c],ss,mid,qind,qval);
	}
	else
	{
		Update(rc[c],mid+1,se,qind,qval);
	}
	sum[c]=min(sum[lc[c]],sum[rc[c]]);
	//printf("%i %i: %i\n",ss,se,sum[c]);
}
void DFSquery(ll u)
{
	ct++;
	Update(1,1,n,ct,dp[u]-pref[u]);
	/*printf("%i: ",u);
	for(int i=1;i<=n;i++)
	{
		printf("%lld ",a[i]);
	}
	printf("\n");*/
	for(ll i=0;i<query[u].size();i++)
	{
		ll x=U[query[u][i].first];
		ll y=V[query[u][i].first];
		if(escaped[query[u][i].second]==true)
		{
			continue;
		}
		ll Root=x;
		if(depth[y]>depth[x]) Root=y;
		ll mn=Get(1,1,n,depth[Root],ct);
		res[query[u][i].second]=pref[u]+mn;
		//printf("%i %i: %lld %i\n",depth[Root],ct,mn,Root);
	}
	for(auto i:E[u])
	{
		if(i.first!=parent[u])
		{
			DFSquery(i.first);
		}
	}
	Update(1,1,n,ct,0);
	ct--;
}
int main()
{
    ll s,q,e;
    scanf("%lld%lld%lld%lld",&n,&s,&q,&e);
    for(ll i=1;i<n;i++)
	{
		scanf("%lld%lld%lld",&U[i],&V[i],&W[i]);
		E[U[i]].push_back({V[i],W[i]});
		E[V[i]].push_back({U[i],W[i]});
		dp[i]=inf;
	}
	dp[n]=inf;
	for(ll i=1;i<=s;i++)
	{
		ll x;
		scanf("%lld",&x);
		store[x]=true;
	}
	ll ind[n+1],R[n+1];
	for(ll i=1;i<=q;i++)
	{
		scanf("%lld%lld",&ind[i],&R[i]);
		query[R[i]].push_back({ind[i],i});
	}
	Build(root,1,n);
	DFSsetup(e);
	DFSexit(e);
	DFSquery(e);
	/*for(int i=1;i<=n;i++)
	{
		printf("%i: %lld\n",i,dp[i]);
	}*/
	for(ll i=1;i<=q;i++)
	{
		if(escaped[i]==true)
		{
			printf("escaped\n");
		}
		else if(res[i]>=inf)
		{
			printf("oo\n");
		}
		else
		{
			printf("%lld\n",res[i]);
		}
	}
    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'void DFSexit(long long int)':
valley.cpp:41:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(ll i=0;i<query[u].size();i++)
      |             ~^~~~~~~~~~~~~~~~
valley.cpp: In function 'void DFSquery(long long int)':
valley.cpp:120:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  for(ll i=0;i<query[u].size();i++)
      |             ~^~~~~~~~~~~~~~~~
valley.cpp: In function 'int main()':
valley.cpp:147:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |     scanf("%lld%lld%lld%lld",&n,&s,&q,&e);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:150:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |   scanf("%lld%lld%lld",&U[i],&V[i],&W[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:159:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |   scanf("%lld",&x);
      |   ~~~~~^~~~~~~~~~~
valley.cpp:165:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |   scanf("%lld%lld",&ind[i],&R[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 27
• Subtask 3: 0 / 23
• Subtask 4: 0 / 41