Submission #126991

#	Time	Username	Problem	Language	Result	Execution time	Memory
126991		TadijaSebez	Valley (BOI19_valley)	C++11	100 / 100	452 ms	114552 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int N=100050;
const ll inf=1e18;
const ll lim=1e17;
const int M=80*N;
int ls[M],rs[M],tsz,root[N];
ll mn[M],lzy[M];
bool shop[N];
vector<pair<int,int>> E[N];
ll dep[N];
int lid[N],rid[N],tid,nod[N],n;
void DFS(int u, int p)
{
	lid[u]=++tid;
	nod[tid]=u;
	for(auto e:E[u]) if(e.first!=p)
	{
		dep[e.first]=dep[u]+e.second;
		DFS(e.first,u);
	}
	rid[u]=tid;
}
void Build(int &c, int ss, int se)
{
	c=++tsz;
	if(ss==se)
	{
		if(shop[nod[ss]]) mn[c]=dep[nod[ss]];
		else mn[c]=inf;
		return;
	}
	int mid=ss+se>>1;
	Build(ls[c],ss,mid);
	Build(rs[c],mid+1,se);
	mn[c]=min(mn[ls[c]],mn[rs[c]]);
}
void Add(int p, int &c, int ss, int se, int qs, int qe, ll x)
{
	if(qs>qe || qs>se || ss>qe) return;
	c=++tsz;ls[c]=ls[p];rs[c]=rs[p];mn[c]=mn[p];lzy[c]=lzy[p];
	if(qs<=ss && qe>=se){ lzy[c]+=x;mn[c]+=x;return;}
	int mid=ss+se>>1;
	Add(ls[p],ls[c],ss,mid,qs,qe,x);
	Add(rs[p],rs[c],mid+1,se,qs,qe,x);
	mn[c]=min(mn[ls[c]],mn[rs[c]])+lzy[c];
}
ll Get(int c, int ss, int se, int qs, int qe)
{
	if(qs>qe || qs>se || ss>qe) return inf;
	if(qs<=ss && qe>=se) return mn[c];
	int mid=ss+se>>1;
	return min(Get(ls[c],ss,mid,qs,qe),Get(rs[c],mid+1,se,qs,qe))+lzy[c];
}
void Build(int u, int p)
{
	Add(root[p],root[u],1,n,lid[u],rid[u],-2*(dep[u]-dep[p]));
	for(auto e:E[u]) if(e.first!=p) Build(e.first,u);
}
bool in(int x, int y){ return lid[x]<=lid[y] && lid[y]<=rid[x];}
struct Edge
{
	int u,v,w;
	Edge(){}
	Edge(int a, int b, int c):u(a),v(b),w(c){}
} edges[N];
int main()
{
	int s,q,e,x,u,v,w;
	scanf("%i %i %i %i",&n,&s,&q,&e);
	for(int i=1;i<n;i++) scanf("%i %i %i",&u,&v,&w),E[u].pb({v,w}),E[v].pb({u,w}),edges[i]=Edge(u,v,w);
    for(int i=1;i<=s;i++) scanf("%i",&u),shop[u]=1;
	DFS(1,0);
	Build(root[0],1,n);
	Build(1,0);
	while(q--)
	{
		scanf("%i %i",&x,&u);
		int a=edges[x].u,b=edges[x].v;
		if(dep[a]<dep[b]) swap(a,b);
		if(in(a,u)==in(a,e)) printf("escaped\n");
		else
		{
			ll ans,d;
            if(in(a,u)) d=Get(root[u],1,n,lid[a],rid[a]);
			else d=min(Get(root[u],1,n,1,lid[a]-1),Get(root[u],1,n,rid[a]+1,n));
			ans=d+dep[u];
			if(ans>=lim) printf("oo\n");
			else printf("%lld\n",ans);
		}
	}
	return 0;
}

Compilation message (stderr)

valley.cpp: In function 'void Build(int&, int, int)':
valley.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
valley.cpp: In function 'void Add(int, int&, int, int, int, int, long long int)':
valley.cpp:45:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
valley.cpp: In function 'long long int Get(int, int, int, int, int)':
valley.cpp:54:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
valley.cpp: In function 'int main()':
valley.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i %i",&n,&s,&q,&e);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:73:79: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<n;i++) scanf("%i %i %i",&u,&v,&w),E[u].pb({v,w}),E[v].pb({u,w}),edges[i]=Edge(u,v,w);
                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
valley.cpp:74:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=s;i++) scanf("%i",&u),shop[u]=1;
                           ~~~~~~~~~~~~~~^~~~~~~~~~
valley.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&x,&u);
   ~~~~~^~~~~~~~~~~~~~~

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