Submission #860193

#	Time	Username	Problem	Language	Result	Execution time	Memory
860193		maks007	Valley (BOI19_valley)	C++14	36 / 100	3053 ms	17092 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;
int root, escape, mn_shop;

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);
	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);
	}
	while(query --) {
		int idx, v;
		cin >> idx >> v;
		idx --, v --;
		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 dfs(long long int, const long long int&, long long int, long long int)':
valley.cpp:17:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |  for(auto [u, w] : g[v]) {
      |           ^

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 0 / 23
• Subtask 4: 0 / 41