Submission #512317

#	Time	Username	Problem	Language	Result	Execution time	Memory
512317		MurotY	Valley (BOI19_valley)	C++14	0 / 100	3092 ms	37784 KiB

valley

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long 
#define ff first
#define ss second
using namespace std;
const int N=1e6+7;
vector <pair <ll,ll>> g[N];
ll a[N], b[N];
bool u[N];
void dfs(ll v, ll p, ll l){
	u[v]=1;
	for (auto it:g[v]){
		if (it.ff != p && it.ss != l){
			dfs(it.ff, v, l);
		}
	}
	return ;
}
int main()
{
	ll n, s, q, e;
	cin >> n >> s >> q >> e;
	
	for (int i=1;i<n;i++){
		int x, y;
		cin >> x >> y >> a[i];
		g[x].push_back({y, i});
		g[y].push_back({x, i});
	}
	map <ll,ll> mp;
	for (int i=1;i<=s;i++) cin >> b[i], mp[b[i]]++;
	while (q--){
		int l, r;
		cin >> l >> r;
		dfs(r, 0, l);
		if (u[r] == u[e] and u[r]){
		     cout <<"escaped\n";
			fill(u, u+n+1, 0);
		} 
		else {
			queue <ll> q;
			vector <ll> dc(n+1, 1e9);
			dc[r]=0;
			q.push(r);
			while (!q.empty()){
				int x=q.front();
				q.pop();
				for (auto l:g[x]){
					if (dc[l.ff] >= dc[x]+a[l.ss]){
						dc[l.ff]=dc[x]+a[l.ss];
						q.push(l.ff);
					}
				}
			}
			ll ans=1e9;
			for (int i=1;i<=n;i++){
				if (mp[i] and u[r] == u[i] and u[r]) ans=min(ans, dc[i]);
			}
			if (ans == 1e9) cout << "oo\n";
			else	cout << ans <<"\n";
			fill(u, u+n+1, 0);
		}
	}
}

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