Submission #226914

#	Time	Username	Problem	Language	Result	Execution time	Memory
226914		Pajaraja	Valley (BOI19_valley)	C++17	100 / 100	328 ms	34552 KiB

valley

#include <bits/stdc++.h>
#define MAXN 100007
#define LINF 1000000000000000000LL
using namespace std;
vector<int> g[MAXN],u[MAXN],ui[MAXN];
vector<long long> w[MAXN];
bool pr[MAXN];
int n,s,q,r,e[MAXN][2],nd[MAXN],db[MAXN];
long long ds[MAXN],ans[MAXN],seg[4*MAXN],opt[MAXN],rs[MAXN];
void upd(int l,int r,int v,long long x,int ind)
{
	if(l==r) {seg[ind]=x; return;}
	int s=(l+r)/2;
	if(v<=s) upd(l,s,v,x,2*ind);
	else upd(s+1,r,v,x,2*ind+1);
	seg[ind]=min(seg[2*ind],seg[2*ind+1]);
}
long long nmin(int l,int r,int lt,int rt,int ind)
{
	if(l>=lt && r<=rt) return seg[ind];
	if(r<lt || l>rt) return LINF;
	int s=(l+r)/2;
	return min(nmin(l,s,lt,rt,2*ind),nmin(s+1,r,lt,rt,2*ind+1));
}
void dfs(int s,int f,int dub,long long dist)
{
	ds[s]=dist;
	db[s]=dub;
	rs[s]=LINF;
	if(pr[s]) rs[s]=ds[s];
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) 
	{
		dfs(g[s][i],s,dub+1,dist+w[s][i]);
		rs[s]=min(rs[s],rs[g[s][i]]);
	}
	opt[s]=rs[s]-2*ds[s];
}
void solve(int s,int f)
{
	nd[s]=db[s];
	upd(0,n,db[s],opt[s],1);
	for(int i=0;i<u[s].size();i++)
	{
		if((nd[e[u[s][i]][1]]==-1) || (nd[e[u[s][i]][0]]==-1)) ans[ui[s][i]]=-1;
		else 
		{
			int lk=max(nd[e[u[s][i]][1]],nd[e[u[s][i]][0]]);
			ans[ui[s][i]]=ds[s]+nmin(0,n,lk,db[s],1);
		}
	}
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) solve(g[s][i],s);
	nd[s]=-1;
}
int main()
{
	scanf("%d%d%d%d",&n,&s,&q,&r);
	for(int i=0;i<n-1;i++)
	{
		int t1,t2; long long t3;
		scanf("%d%d%lld",&t1,&t2,&t3);
		g[t1].push_back(t2);
		g[t2].push_back(t1);
		w[t1].push_back(t3);
		w[t2].push_back(t3);
		e[i+1][0]=t1; e[i+1][1]=t2;
	}
	for(int i=0;i<s;i++)
	{
		int t;
		scanf("%d",&t);
		pr[t]=true;
	}
	for(int i=0;i<q;i++)
	{
		int t1,t2;
		scanf("%d%d",&t1,&t2);
		u[t2].push_back(t1);
		ui[t2].push_back(i);
	}
	fill(nd,nd+MAXN,-1);
	fill(seg,seg+4*MAXN,LINF);
	dfs(r,r,0,0);
	solve(r,r);
	for(int i=0;i<q;i++) 
	{
		if(ans[i]==-1) printf("escaped\n");
		else 
		{
			if(ans[i]>100000000000000000LL) printf("oo\n");
			else printf("%lld\n",ans[i]);
		}
	}
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(int, int, int, long long int)':
valley.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) 
              ~^~~~~~~~~~~~
valley.cpp: In function 'void solve(int, int)':
valley.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u[s].size();i++)
              ~^~~~~~~~~~~~
valley.cpp:51:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) solve(g[s][i],s);
              ~^~~~~~~~~~~~
valley.cpp: In function 'int main()':
valley.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&n,&s,&q,&r);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld",&t1,&t2,&t3);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&t);
   ~~~~~^~~~~~~~~
valley.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&t1,&t2);
   ~~~~~^~~~~~~~~~~~~~~~

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