Submission #243333

#	Time	Username	Problem	Language	Result	Execution time	Memory
243333		Lawliet	Valley (BOI19_valley)	C++17	100 / 100	308 ms	55032 KiB

valley

#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;
typedef pair<int,int> pii;

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];

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

bool isSpecial[MAXN];

pii edges[MAXN];

vector<int> adj[MAXN];
vector<int> weight[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;
	tin[cur] = ++curTime;

	if( isSpecial[cur] ) 
		nextSub[cur] = depthW[cur];

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

		if( viz == p ) continue;

		depth[viz] = depth[cur] + 1;
		depthW[viz] = depthW[cur] + w;

		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++)
	{
		int U, V, W;
		scanf("%d %d %d",&U,&V,&W);

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

		weight[U].push_back( W );
		weight[V].push_back( W );

		edges[i] = { U , V };
	}

	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++)
	{
		int U = edges[i].first;
		int V = edges[i].second;

		if( depthW[U] > depthW[V] ) 
			swap( edges[i].first , edges[i].second );
	}

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

		int p = edges[ind].second;

		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:41: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:89: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:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&U,&V,&W);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
valley.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&shop);
   ~~~~~^~~~~~~~~~~~
valley.cpp:141: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