제출 #898810

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
898810		vjudge1	Valley (BOI19_valley)	C++17	0 / 100	7 ms	2648 KiB

valley

//In the name of GOD***---...---***---...---***---...

/*/=======================================

Diversity in counsel, unity in command
__
Success always calls for greater generosity - though
most people, lost in the darkness of their own egos,
treat it as an occasion for greater greed.
Collecting boot is not an end itself, but only a means for
building an empire. Riches would be of little use to us now
except as a means of winning new friends.
__*By Cyrus the great*__

=======================================/*/
#include<bits/stdc++.h>
using namespace std;
////========== Defines ==============////
#define IOS ios_base::sync_with_stdio(0);\
	cin.tie(0);\
	cout.tie(0);
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define fixed(a) fixed<<setprecision(a)
////=============== Typedefs ==============////
typedef long long int lli;
typedef pair<int,int> pii;
////=============== CONSTANT ===============////
const lli mx = (1e3+100)*5, inf = (1<<30);
////============== Global types ============////
vector<pii> adj[mx];
int n, s, q, e, mini =inf, ban1, ban2;
pii ed[mx];
int wi[mx][mx], st[mx], dis[mx];
////========== User Define Functions ==========////
void dfs(int p, int v){
//	cout << v << '\n';
	if(v == e) mini = -1;
	dis[v] =dis[p] + wi[p][v];
	if(st[v] == 1) {
		mini = min(mini, dis[v]);
	}
	for(auto u : adj[v]) if(!(u.F == p || (v == ban1 && u.F == ban2) || (v == ban2 && u.F == ban1))) dfs(v, u.F);
}
void solve(int ban, int pos) {
	mini =inf;
	if(n == s){
		if(pos == e) cout << 0 << '\n';
		else cout << "escape\n";
	}
	else{
		dfs(0, pos);
		if(mini == -1){
			cout << "escape\n";
			return;
		}
		if(mini == inf){
			cout << "oo";
			return;
		}
		cout << mini << '\n';
	}
}
////================= Notes =================////
/*

*/
////============ End of Templates ============////
int main() {
	IOS
	cin >> n >> s >> q >> e;
	for(int i =1; i <= n-1; i++) {
		int x, y, w;
		cin >> x >> y >> w;
		ed[i] = mp(x, y);
		wi[x][y] = w;
		wi[y][x] =w;
		adj[x]. pb(mp(y, w));
		adj[y]. pb(mp(x, w));
	}
	for(int i =0; i < s; i++) {
		int x; cin >> x;
		st[x] =1;
	}
	while(q--){
		int ban, pos;
		cin >> ban >> pos;
		ban1 = ed[ban].F; ban2 = ed[ban].S;
		solve(ban, pos);
	}
	;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
	return 0;

}
//Hewwo OwO

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