Submission #1270918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270918		efeg	Valley (BOI19_valley)	C++20	36 / 100	3090 ms	12628 KiB

valley

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

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#define int long long 
#define F first
#define S second 
#define pb push_back
#define endl '\n'
#define all(v) v.begin(),v.end()
#define gcd(a,b) __gcd(a,b)
#define mt make_tuple
#define pqueue priority_queue


typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<iii> viii;
typedef set<int> si;
typedef vector<ii> vii;				
typedef vector<vi> vvi;
typedef vector<si> vsi;
typedef vector<vb> vvb;
typedef vector<vc> vvc;

const int MOD = 1e9 + 7;
const int N = 2e5 + 100;

int n,s,q,e; 
vector<viii> adj; 
vi v,vis;
int qi,qr; 

void _(){
	cin >> n >> s >> q >> e; e--; 
	adj.assign(n+10,viii()); 
	v.assign(n+10,false); 
	for (int i = 0; i < n-1; i++){
		int a,b,w; cin >> a >> b >> w;
		a--; b--;
		adj[a].emplace_back(b,w,i); 
		adj[b].emplace_back(a,w,i); 
	}
	for (int i = 0; i < s; i++){
		int x; cin >> x; x--;
		v[x] = true; 
	}
	for (int i = 0; i < q; i++){
		cin >> qi >> qr; qi--; qr--; 
		pqueue<ii,vii,greater<ii>> pq;
		vis.assign(n + 10, INT_MAX); 
		pq.push({0,qr}); 
		
		bool escaped = false; 
		int ans = -1; 
		while (!pq.empty()){
			int d,node; tie(d,node) = pq.top(); pq.pop(); 
			if (vis[node] != INT_MAX) continue;
			vis[node] = d;
			if (node == e){
				escaped = true;
				break; 
			}
			if (v[node] && ans == -1) ans = d;

			for (auto tp : adj[node]){
				int to,w,idx; tie(to,w,idx) = tp;
				if (idx == qi) continue;
				if (vis[node] != INT_MAX) pq.push({d + w ,to}); 
			}
		}
		if (escaped) cout << "escaped" << endl;
		else {
			if (ans != -1) cout << ans << endl;
			else cout << "oo" << endl; 
		}


	}


}

int32_t main(){
	ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	int t = 1;// cin >> t;
	while (t--){
		_(); 
	}

	return 0;
}	

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