Submission #170313

#	Time	Username	Problem	Language	Result	Execution time	Memory
170313		ngmh	Valley (BOI19_valley)	C++11	36 / 100	3025 ms	13640 KiB

valley

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second

typedef long long ll;
typedef pair<ll, ll> pi;

ll n, s, q, e, a, b, w, z, r, c[100005];
vector<pi> adj[100005];
pi rs[100005];
	
ll dfs(ll x, ll p){
	ll best = LLONG_MAX/3;
	if(x == e) return -1;
	for(auto it : adj[x]){
		if(it.F == rs[z].F && x == rs[z].S) continue;
		if(it.F == rs[z].S && x == rs[z].F) continue;
		if(it.F != p){
			ll cur = dfs(it.F, x);
			if(cur == -1) return cur;
			best = min(best, cur+it.S);
		}
	}
	if(c[x]) return 0;
	return best;
}

int main(){
	cin >> n >> s >> q >> e;
	for(ll i = 0; i < n-1; i++){
		cin >> a >> b >> w;
		adj[a].push_back(pi(b, w));
		adj[b].push_back(pi(a, w));
		rs[i] = pi(a, b);
	}
	for(ll i = 0; i < s; i++){ cin >> z; c[z] = 1; }
	for(ll i = 0; i < q; i++){
		cin >> z >> r; z--;
		ll ans = dfs(r, -1);
		if(ans == -1) cout << "escaped\n";
		else if(ans >= LLONG_MAX/3) cout << "oo\n";
		else cout << ans << "\n";
	}
}

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