oj.uz

Submission #860204

# Submission time Handle Problem Language Result Execution time Memory
860204 2023-10-12T06:12:42 Z maks007 Valley (BOI19_valley) C++14
59 / 100
 3000 ms 46860 KB 
#include "bits/stdc++.h"

using namespace std;

#define int long long

vector <vector <pair <int,int>>> g;
set <int> shop;
vector <pair <int,int>> edge;
vector <int> deep;
int root, escape, mn_shop, jmp[(int)1e5][32];

void count_depth(int v, int p = -1, int depth = 0) {
	deep[v] = depth;
	jmp[v][0]=p;
	for(auto [u, w] : g[v]) {
		if(u == p) continue;
		count_depth(u, v, depth+1);
	}
}

int get(int k, int n) {
	for(int i = 31; i >= 0; i --) {
		if(k - (1LL << i) >= 0) {
			n = jmp[n][i];
			if(n == -1) return n;
			k -= (1LL << i);
		}
	}
	return n;
}

void dfs(int v, const int &idx, int p = -1, int dist = 0) {
	if(v == root) {
		escape = 1;
	}
	if(shop.count(v)) mn_shop = min(mn_shop, dist);
	for(auto [u, w] : g[v]) {
		if(u == p) continue;
		if(u == edge[idx].first && v == edge[idx].second) continue;
		if(u == edge[idx].second && v == edge[idx].first) continue;
		dfs(u, idx, v, dist + w);
	}
}

signed main () {
	int n, shopsz, query;
	cin >> n >> shopsz >> query >> root;
	root --;
	g.resize(n);
	deep.resize(n);
	for(int i = 0; i < n - 1; i ++) {
		int u, v;
		cin >> u >> v;
		u --, v --;
		int w;
		cin >> w;
		g[v].push_back({u, w});
		g[u].push_back({v, w});
		edge.push_back({u, v});
	}
	while(shopsz --) {
		int x;
		cin >> x;
		shop.insert(x-1);
	}
	count_depth(root);
	if(shop.size() == n) {
		for(int dist = 1; dist < 32; dist ++) {
			for(int i = 0; i < n; i ++) {
				if(jmp[i][dist-1] == -1) jmp[i][dist] = -1;
				else jmp[i][dist] = jmp[jmp[i][dist-1]][dist-1];
			}
		}
	}
	while(query --) {
		int idx, v;
		cin >> idx >> v;
		idx --, v --;
		if(shop.size() == n) {
			// cout << "*";
			if(deep[edge[idx].first] < deep[edge[idx].second]) swap(edge[idx].first, edge[idx].second);
			int which = edge[idx].first;
			if(deep[which] > deep[v]) {
				cout << "escaped\n";
				continue;
			}
			int dist = deep[v] - deep[which];
			// cout << dist << " " << which + 1 << " " << get(dist, v) + 1 << "\n";
			if(get(dist, v) == which) cout << 0 << "\n";
			else cout << "escaped\n";
			continue;
		}
		escape = 0;
		mn_shop = LLONG_MAX;
		dfs(v, idx);
		if(escape) {
			cout << "escaped\n";
		}else if(mn_shop != LLONG_MAX) {
			cout << mn_shop << "\n";
		}else cout << "oo\n";
	}
	return 0;
}

Compilation message

valley.cpp: In function 'void count_depth(long long int, long long int, long long int)':
valley.cpp:16:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |  for(auto [u, w] : g[v]) {
      |           ^
valley.cpp: In function 'void dfs(long long int, const long long int&, long long int, long long int)':
valley.cpp:38:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |  for(auto [u, w] : g[v]) {
      |           ^
valley.cpp: In function 'int main()':
valley.cpp:68:17: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   68 |  if(shop.size() == n) {
      |     ~~~~~~~~~~~~^~~~
valley.cpp:80:18: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   80 |   if(shop.size() == n) {
      |      ~~~~~~~~~~~~^~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 344 KB Output is correct
2 Correct 21 ms 344 KB Output is correct
3 Correct 24 ms 344 KB Output is correct
4 Correct 15 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 344 KB Output is correct
2 Correct 21 ms 344 KB Output is correct
3 Correct 24 ms 344 KB Output is correct
4 Correct 15 ms 348 KB Output is correct
5 Correct 9 ms 2652 KB Output is correct
6 Correct 11 ms 2652 KB Output is correct
7 Correct 13 ms 2652 KB Output is correct
8 Correct 11 ms 2648 KB Output is correct
9 Correct 12 ms 2652 KB Output is correct
10 Correct 19 ms 2796 KB Output is correct
11 Correct 3 ms 2652 KB Output is correct
12 Correct 3 ms 2652 KB Output is correct
13 Correct 3 ms 2652 KB Output is correct
14 Correct 21 ms 2648 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 40632 KB Output is correct
2 Correct 347 ms 44292 KB Output is correct
3 Correct 333 ms 44524 KB Output is correct
4 Correct 378 ms 45576 KB Output is correct
5 Correct 353 ms 45816 KB Output is correct
6 Correct 360 ms 46860 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 344 KB Output is correct
2 Correct 21 ms 344 KB Output is correct
3 Correct 24 ms 344 KB Output is correct
4 Correct 15 ms 348 KB Output is correct
5 Correct 9 ms 2652 KB Output is correct
6 Correct 11 ms 2652 KB Output is correct
7 Correct 13 ms 2652 KB Output is correct
8 Correct 11 ms 2648 KB Output is correct
9 Correct 12 ms 2652 KB Output is correct
10 Correct 19 ms 2796 KB Output is correct
11 Correct 3 ms 2652 KB Output is correct
12 Correct 3 ms 2652 KB Output is correct
13 Correct 3 ms 2652 KB Output is correct
14 Correct 21 ms 2648 KB Output is correct
15 Correct 333 ms 40632 KB Output is correct
16 Correct 347 ms 44292 KB Output is correct
17 Correct 333 ms 44524 KB Output is correct
18 Correct 378 ms 45576 KB Output is correct
19 Correct 353 ms 45816 KB Output is correct
20 Correct 360 ms 46860 KB Output is correct
21 Execution timed out 3032 ms 38040 KB Time limit exceeded
22 Halted 0 ms 0 KB -