Submission #860204

#	Time	Username	Problem	Language	Result	Execution time	Memory
860204		maks007	Valley (BOI19_valley)	C++14	59 / 100	3032 ms	46860 KiB

valley

#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 (stderr)

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 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 0 / 41