oj.uz

Submission #926620

# Submission time Handle Problem Language Result Execution time Memory
926620 2024-02-13T12:42:14 Z denniskim Valley (BOI19_valley) C++17
36 / 100
 3000 ms 49820 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

ll n, s, q, e;
ll all, bll, cll;
vector<pll> edg, vec[100010];
ll a[100010];
ll IN[100010], OUT[100010];
ll cc, P[100010];
ll dp[100010], dep[100010];
ll spa[100010][21], minn[100010][21];

void dfs0(ll here, ll pa)
{
	IN[here] = ++cc;
	P[here] = pa;
	spa[here][0] = pa;
	
	for(auto &i : vec[here])
	{
		if(i.fi == pa)
			continue;
		
		dep[i.fi] = dep[here] + i.se;
		dfs0(i.fi, here);
	}
	
	OUT[here] = cc;
}

void dfs(ll here, ll pa)
{
	for(auto &i : vec[here])
	{
		if(i.fi == pa)
			continue;
		
		dfs(i.fi, here);
		dp[here] = min(dp[here], dp[i.fi]);
	}
}

int main(void)
{
	fastio
	
	cin >> n >> s >> q >> e;
	
	for(ll i = 1 ; i < n ; i++)
	{
		cin >> all >> bll >> cll;
		
		edg.push_back({all, bll});
		vec[all].push_back({bll, cll});
		vec[bll].push_back({all, cll});
	}
	
	for(ll i = 1 ; i <= n ; i++)
		dp[i] = INF;
	
	for(ll i = 1 ; i <= s ; i++)
		cin >> a[i];
	
	dfs0(e, 0);
	
	for(ll i = 1 ; i <= s ; i++)
		dp[a[i]] = dep[a[i]];
	
	dfs(e, 0);
	
	for(ll i = 1 ; i <= n ; i++)
	{
		dp[i] -= 2 * dep[i];
		minn[i][0] = dp[i];
	}
	
	for(ll i = 1 ; i <= 20 ; i++)
	{
		for(ll j = 1 ; j <= n ; j++)
		{
			spa[j][i] = spa[spa[j][i - 1]][i - 1];
			minn[j][i] = min(minn[j][i - 1], minn[spa[j][i - 1]][i - 1]);
		}
	}
	
	while(q--)
	{
		cin >> bll >> all;
		
		pll E = edg[bll - 1];
		
		if(dep[E.fi] < dep[E.se])
			swap(E.fi, E.se);
		
		if(!(IN[E.fi] <= IN[all] && OUT[all] <= OUT[E.fi]))
		{
			cout << "escaped\n";
			continue;
		}
		
		ll gaet = dep[all] - dep[E.fi] + 1;
		ll ans = INF;
		ll now = all;
		
		/*for(ll i = 20 ; i >= 0 ; i--)
		{
			if(gaet >= (1LL << i))
			{
				gaet -= (1LL << i);
				ans = min(ans, minn[now][i] + dep[all]);
				now = spa[now][i];
			}
		}*/
		
		for(ll i = all ; i != E.fi ; i = spa[i][0])
			ans = min(ans, dep[all] + dp[i]);
		
		ans = min(ans, dep[all] + dp[E.fi]);
		
		if(ans >= INF / 100)
			cout << "oo\n";
		else
			cout << ans en;
	}
	
	return 0;
}

Compilation message

valley.cpp: In function 'int main()':
valley.cpp:116:6: warning: unused variable 'gaet' [-Wunused-variable]
  116 |   ll gaet = dep[all] - dep[E.fi] + 1;
      |      ^~~~
valley.cpp:118:6: warning: unused variable 'now' [-Wunused-variable]
  118 |   ll now = all;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9308 KB Output is correct
2 Correct 4 ms 9564 KB Output is correct
3 Correct 3 ms 9560 KB Output is correct
4 Correct 3 ms 9564 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9308 KB Output is correct
2 Correct 4 ms 9564 KB Output is correct
3 Correct 3 ms 9560 KB Output is correct
4 Correct 3 ms 9564 KB Output is correct
5 Correct 2 ms 11608 KB Output is correct
6 Correct 3 ms 11608 KB Output is correct
7 Correct 2 ms 11612 KB Output is correct
8 Correct 3 ms 11660 KB Output is correct
9 Correct 3 ms 11612 KB Output is correct
10 Correct 3 ms 11612 KB Output is correct
11 Correct 3 ms 11612 KB Output is correct
12 Correct 4 ms 11612 KB Output is correct
13 Correct 3 ms 11532 KB Output is correct
14 Correct 3 ms 11608 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 47520 KB Output is correct
2 Correct 102 ms 47336 KB Output is correct
3 Correct 128 ms 47708 KB Output is correct
4 Correct 1188 ms 48844 KB Output is correct
5 Correct 2492 ms 49128 KB Output is correct
6 Execution timed out 3049 ms 49820 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9308 KB Output is correct
2 Correct 4 ms 9564 KB Output is correct
3 Correct 3 ms 9560 KB Output is correct
4 Correct 3 ms 9564 KB Output is correct
5 Correct 2 ms 11608 KB Output is correct
6 Correct 3 ms 11608 KB Output is correct
7 Correct 2 ms 11612 KB Output is correct
8 Correct 3 ms 11660 KB Output is correct
9 Correct 3 ms 11612 KB Output is correct
10 Correct 3 ms 11612 KB Output is correct
11 Correct 3 ms 11612 KB Output is correct
12 Correct 4 ms 11612 KB Output is correct
13 Correct 3 ms 11532 KB Output is correct
14 Correct 3 ms 11608 KB Output is correct
15 Correct 97 ms 47520 KB Output is correct
16 Correct 102 ms 47336 KB Output is correct
17 Correct 128 ms 47708 KB Output is correct
18 Correct 1188 ms 48844 KB Output is correct
19 Correct 2492 ms 49128 KB Output is correct
20 Execution timed out 3049 ms 49820 KB Time limit exceeded
21 Halted 0 ms 0 KB -