Submission #243337

#	Time	Username	Problem	Language	Result	Execution time	Memory
243337		Lawliet	Valley (BOI19_valley)	C++17	100 / 100	294 ms	52088 KiB

valley

#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int LOG = 20;
const int MAXN = 100010;
const lli INF = 1000000000000000000LL;

int n, s, q;
int root, curTime;

int depth[MAXN];
int tin[MAXN], tout[MAXN];
int U[MAXN], V[MAXN], W[MAXN];

lli nextSub[MAXN], depthW[MAXN];
lli tab[LOG][MAXN], mn[LOG][MAXN];

bool isSpecial[MAXN];

vector<int> adj[MAXN];
vector<int> indEdge[MAXN];

lli getValue(int cur) 
{ 
	if( nextSub[cur] == INF ) return INF;
	return nextSub[cur] - 2*depthW[cur]; 
}

void DFS(int cur, int p)
{
	nextSub[cur] = INF;
	if( isSpecial[cur] ) nextSub[cur] = depthW[cur];

	tin[cur] = ++curTime;

	for(int i = 0 ; i < adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];
		int ind = indEdge[cur][i];

		if( viz == p ) continue;

		depth[viz] = depth[cur] + 1;
		depthW[viz] = depthW[cur] + W[ind];

		DFS( viz , cur );

		nextSub[cur] = min( nextSub[cur] , nextSub[viz] );
	}

	tab[0][cur] = p;
	mn[0][cur] = getValue( cur );

	tout[cur] = curTime;
}

bool reachExit(int p, int cur)
{
	bool inSubtree = ( tin[p] <= tin[cur] );
	inSubtree = inSubtree && ( tout[cur] <= tout[p] );

	return !inSubtree;
}

lli query(int p, int cur)
{
	lli ans = INF;
	int d = depth[cur] - depth[p] + 1;

	for(int k = 0 ; k < LOG ; k++)
	{
		if( d & (1 << k) )
		{
			ans = min( ans , mn[k][cur] );
			cur = tab[k][cur];
		}
	}

	return ans;
}

int main()
{
	scanf("%d %d %d %d",&n,&s,&q,&root);

	for(int k = 0 ; k < LOG ; k++)
		mn[k][0] = INF;

	for(int i = 1 ; i < n ; i++)
	{
		scanf("%d %d %d",&U[i],&V[i],&W[i]);

		adj[ U[i] ].push_back( V[i] );
		adj[ V[i] ].push_back( U[i] );

		indEdge[ U[i] ].push_back( i );
		indEdge[ V[i] ].push_back( i );
	}

	for(int i = 1 ; i <= s ; i++)
	{
		int shop;
		scanf("%d",&shop);

		isSpecial[shop] = true;
	}

	DFS( root , 0 );

	for(int k = 1 ; k < LOG ; k++)
	{
		for(int i = 1 ; i <= n ; i++)
		{
			int jump = tab[k - 1][i];

			tab[k][i] = tab[k - 1][jump];
			mn[k][i] = min( mn[k - 1][i] , mn[k - 1][jump] );
		}
	}

	for(int i = 1 ; i < n ; i++)
		if( depth[ U[i] ] > depth[ V[i] ] ) swap( U[i] , V[i] ); 

	for(int i = 1 ; i <= q ; i++)
	{
		int ind, node;
		scanf("%d %d",&ind,&node);

		int p = V[ind];

		if( reachExit( p , node ) )
		{
			printf("escaped\n");
			continue;
		}

		lli ans = query( p , node );

		if( ans == INF ) printf("oo\n");
		else printf("%lld\n",ans + depthW[node]);
	}
}

Compilation message (stderr)

valley.cpp: In function 'void DFS(int, int)':
valley.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
valley.cpp: In function 'int main()':
valley.cpp:86: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,&root);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&U[i],&V[i],&W[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&shop);
   ~~~~~^~~~~~~~~~~~
valley.cpp:129:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&ind,&node);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

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