oj.uz

답안 #243337

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
243337 2020-06-30T23:29:38 Z Lawliet Valley (BOI19_valley) C++17
100 / 100
 294 ms 52088 KB 
#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

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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 5376 KB Output is correct
2 Correct 11 ms 5376 KB Output is correct
3 Correct 10 ms 5504 KB Output is correct
4 Correct 12 ms 5376 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 5376 KB Output is correct
2 Correct 11 ms 5376 KB Output is correct
3 Correct 10 ms 5504 KB Output is correct
4 Correct 12 ms 5376 KB Output is correct
5 Correct 9 ms 5760 KB Output is correct
6 Correct 9 ms 5760 KB Output is correct
7 Correct 9 ms 5664 KB Output is correct
8 Correct 9 ms 5760 KB Output is correct
9 Correct 9 ms 5760 KB Output is correct
10 Correct 9 ms 5760 KB Output is correct
11 Correct 9 ms 5812 KB Output is correct
12 Correct 9 ms 5760 KB Output is correct
13 Correct 10 ms 5760 KB Output is correct
14 Correct 9 ms 5760 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 221 ms 47840 KB Output is correct
2 Correct 246 ms 47340 KB Output is correct
3 Correct 252 ms 47224 KB Output is correct
4 Correct 288 ms 49060 KB Output is correct
5 Correct 262 ms 49120 KB Output is correct
6 Correct 284 ms 51264 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 5376 KB Output is correct
2 Correct 11 ms 5376 KB Output is correct
3 Correct 10 ms 5504 KB Output is correct
4 Correct 12 ms 5376 KB Output is correct
5 Correct 9 ms 5760 KB Output is correct
6 Correct 9 ms 5760 KB Output is correct
7 Correct 9 ms 5664 KB Output is correct
8 Correct 9 ms 5760 KB Output is correct
9 Correct 9 ms 5760 KB Output is correct
10 Correct 9 ms 5760 KB Output is correct
11 Correct 9 ms 5812 KB Output is correct
12 Correct 9 ms 5760 KB Output is correct
13 Correct 10 ms 5760 KB Output is correct
14 Correct 9 ms 5760 KB Output is correct
15 Correct 221 ms 47840 KB Output is correct
16 Correct 246 ms 47340 KB Output is correct
17 Correct 252 ms 47224 KB Output is correct
18 Correct 288 ms 49060 KB Output is correct
19 Correct 262 ms 49120 KB Output is correct
20 Correct 284 ms 51264 KB Output is correct
21 Correct 216 ms 47880 KB Output is correct
22 Correct 223 ms 47360 KB Output is correct
23 Correct 226 ms 47200 KB Output is correct
24 Correct 263 ms 49256 KB Output is correct
25 Correct 257 ms 52088 KB Output is correct
26 Correct 201 ms 47992 KB Output is correct
27 Correct 214 ms 47400 KB Output is correct
28 Correct 231 ms 47328 KB Output is correct
29 Correct 281 ms 48608 KB Output is correct
30 Correct 294 ms 50172 KB Output is correct
31 Correct 205 ms 47996 KB Output is correct
32 Correct 211 ms 47416 KB Output is correct
33 Correct 246 ms 47432 KB Output is correct
34 Correct 244 ms 49144 KB Output is correct
35 Correct 246 ms 52088 KB Output is correct
36 Correct 233 ms 49488 KB Output is correct