Submission #639963

#	Time	Username	Problem	Language	Result	Execution time	Memory
639963		StefanSebez	Valley (BOI19_valley)	C++14	0 / 100	166 ms	18576 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+50;
const ll inf=LONG_MAX;
bool store[N];
bool escaped[N];
int U[N],V[N],W[N];
int depth[N],ct=0;
ll dp[N];
int parent[N];
vector<pair<int,int>>E[N];
vector<pair<int,int>>query[N];
vector<int>nodes;
ll res[N];
ll pref[N];
void DFSsetup(int 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(int u)
{
	nodes.push_back(u);
	for(int i=0;i<query[u].size();i++)
	{
		int x=U[query[u][i].first];
		int 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();
}
int a[N],lc[2*N],rc[2*N],nc,root,sum[N];
int n;
void Build(int &c,int ss,int se)
{
	nc++;
	c=nc;
	if(ss==se)
	{
		sum[c]=0;
		return;
	}
	int 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(int c,int ss,int se,int qs,int qe)
{
	if(qs<=ss && se<=qe)
	{
		return sum[c];
	}
	if(qe<ss || se<qs)
	{
		return inf;
	}
	int mid=(ss+se)/2;
	return min(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
}
void Update(int c,int ss,int se,int qind,int qval)
{
	if(ss==se)
	{
		a[ss]=qval;
		sum[c]=qval;
		//printf("%i %i: %i\n",ss,se,sum[c]);
		return;
	}
	int 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(int u)
{
	ct++;
	Update(1,1,n,ct,dp[u]-pref[u]);
	/*printf("%i: ",u);
	for(int i=1;i<=n;i++)
	{
		printf("%i ",a[i]);
	}
	printf("\n");*/
	for(int i=0;i<query[u].size();i++)
	{
		int x=U[query[u][i].first];
		int y=V[query[u][i].first];
		if(escaped[query[u][i].second]==true)
		{
			continue;
		}
		int 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()
{
    int s,q,e;
    scanf("%i%i%i%i",&n,&s,&q,&e);
    for(int i=1;i<n;i++)
	{
		scanf("%i%i%i",&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(int i=1;i<=s;i++)
	{
		int x;
		scanf("%i",&x);
		store[x]=true;
	}
	int ind[n+1],R[n+1];
	for(int i=1;i<=q;i++)
	{
		scanf("%i%i",&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: %i\n",i,pref[i]);
	}*/
	for(int 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(int)':
valley.cpp:41:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i=0;i<query[u].size();i++)
      |              ~^~~~~~~~~~~~~~~~
valley.cpp: In function 'void DFSquery(int)':
valley.cpp:119:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |  for(int i=0;i<query[u].size();i++)
      |              ~^~~~~~~~~~~~~~~~
valley.cpp: In function 'int main()':
valley.cpp:146:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |     scanf("%i%i%i%i",&n,&s,&q,&e);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:149:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |   scanf("%i%i%i",&U[i],&V[i],&W[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:158:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |   scanf("%i",&x);
      |   ~~~~~^~~~~~~~~
valley.cpp:164:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |   scanf("%i%i",&ind[i],&R[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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