Submission #201228

#	Time	Username	Problem	Language	Result	Execution time	Memory
201228		Lawliet	Valley (BOI19_valley)	C++17	32 / 100	348 ms	54264 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;
int curTime;

int tin[MAXN];
int tout[MAXN];

lli prof[MAXN];
lli nextSub[MAXN];
lli dp[LOG][MAXN];
lli mn[LOG][MAXN];

bool isSpecial[MAXN];

pii edges[MAXN];

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

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

void DFS(int cur, int p)
{
	nextSub[cur] = INF;
	tin[cur] = ++curTime;

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

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

		if( viz == p ) continue;

		dp[0][viz] = cur;
		prof[viz] = prof[cur] + w;

		DFS( viz , cur );

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

	mn[0][cur] = min( getValue(cur) , getValue(p) );

	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 = getValue( cur );

	for(int k = LOG - 1 ; k >= 0 ; k--)
	{
		int jump = dp[k][cur];

		if( jump != 0 && prof[jump] >= prof[p] )
		{
			ans = min( ans , mn[k][cur] );
			cur = dp[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 );

		peso[U].push_back( W );
		peso[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 = dp[k - 1][i];

			dp[k][i] = dp[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( prof[U] > prof[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 + prof[node]);
	}
}

Compilation message (stderr)

valley.cpp: In function 'void DFS(int, int)':
valley.cpp:43: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:91: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:99: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:113:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&shop);
   ~~~~~^~~~~~~~~~~~
valley.cpp:142: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: 0 / 27
• Subtask 3: 23 / 23
• Subtask 4: 0 / 41