Submission #868458

#	Time	Username	Problem	Language	Result	Execution time	Memory
868458		Nuraly_Serikbay	Valley (BOI19_valley)	C++17	23 / 100	84 ms	31128 KiB

valley

//çalışan kazanır//
 
#include "bits/stdc++.h"
 
using namespace std;
 
#define int long long
#define pb push_back
#define S second
#define F first
#define all(x) x.begin(),x.end()
#define YOSIK() ios_base::sync_with_stdio(0),cin.tie(0)
int gcd (int a, int b) {if (b == 0){return a;}else {return gcd (b, a % b);}}
 
const int N = 4e5 + 15;
const int INF = 1e18;
const int MOD = 1e9 + 7;
const int MODD = 1070234587ll;
const double eps = 0.0001;
const int p = 87;

int n, dst[N], tin[N], tout[N], depth[N], q, s, t, e;
pair <int, int> reb[N];
vector <pair <int, int>> g[N]; 

void dfs (int v, int p) {
	tin[v] = ++t;
	for (auto to: g[v]) {
		if (to.F == p) continue;
		depth[to.F] = depth[v] + to.S;
		dfs (to.F, v);
		dst[v] = min (dst[v], (int)(dst[to.F] + to.S));
	}
	tout[v] = t;
	return;
}

void solution () {
	cin >> n >> s >> q >> e;
	for (int i = 1; i < n; ++ i) {
		int v, u, w;
		cin >> v >> u >> w;
		g[v].pb ({u, w});
		g[u].pb ({v, w});
		reb[i] = {v, u};
	}
	for (int i = 1; i <= n; ++ i) dst[i] = INF;
	for (int i = 1; i <= s; ++ i) {
		int x; cin >> x;
		dst[x] = 0;
	}
	dfs (e, 0);
	while (q --) {
		int v, idx;
		cin >> v >> idx;
		swap (v, idx);
		int u = reb[idx].F, ans = INF;
		if (depth[u] < depth[reb[idx].S]) u = reb[idx].S;
		if (tin[u] <= tin[v] && tout[v] <= tout[u]) {
			ans = dst[v];
			ans = min (ans, dst[u] + (depth[v] - depth[u]));
			if (ans == INF) cout << "oo\n";
			else cout << ans << '\n';
		} else cout << "escaped\n";
	}
	return;	
}
 
signed main() {
	YOSIK();
//	srand (time(0));
//	freopen ("E.in", "r", stdin);
//	freopen ("E.out", "w", stdout);
	int TT = 1;// cin >> TT;
	for (int i = 1; i <= TT; ++ i) {
//		cout << "Case " << i << ": ";
		solution ();
		
  	}
 
	return 0;
}

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