Submission #496445

#	Time	Username	Problem	Language	Result	Execution time	Memory
496445		Ierus	Valley (BOI19_valley)	C++17	36 / 100	3086 ms	12556 KiB

valley

#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/
using namespace std;
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
#define eb emplace_back
#define int long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
const int E = 1e6+777;
const long long inf = 1e18+777;
const int N = 1e5+777;
const int MOD = 1e9+7;
const bool I = 1;
int n, s, q, e;
bool mag[N];
bitset<N> used;
int x[N], y[N], w[N];
struct D{
	int v, w, id;
};
vector<D> g[N];
bool dfs(int v, int &pp, int p = 1){
//	cerr << "v: " << v << '\n';
	if(v == e){
		return true;	
	}
	used[v] = true;
	bool res = false;
	for(auto to : g[v]){
		if(!used[to.v] && to.id != pp){
			res |= dfs(to.v, pp, v);
		}
	}
	return res;
}
int Find(int v, int pp){
	int res = LLONG_MAX;
	vector<int> d(n+1, LLONG_MAX);
	set<pair<int,int>> st = {{d[v]=0,v}};
	while(!st.empty()){
		v = st.begin() -> S;
		st.erase(st.begin());
		if(mag[v]){
			res = min(res, d[v]);
		}
		for(auto to : g[v]){
			if(d[to.v] > d[v] + to.w && to.id != pp){
				st.erase({d[to.v], to.v});
				d[to.v] = d[v] + to.w;
				st.insert({d[to.v], to.v});
			}
		}
	}
	return res;
}
signed main(){NFS;
	cin >> n >> s >> q >> e;
	for(int i = 1; i < n; ++i){
		cin >> x[i] >> y[i] >> w[i];
		g[x[i]].pb({y[i], w[i], i});
		g[y[i]].pb({x[i], w[i], i});
	}
	for(int i = 1; i <= s; ++i){
		int xx; cin >> xx;
		mag[xx] = true;
	}
	for(int i = 1; i <= q; ++i){
		int pp, h;
		cin >> pp >> h;
		used.reset();
//		int cur = dfs(h, pp);
//		cerr << "dfs("<<h<<','<<"pp"<<"): " << cur << '\n';
//		exit(false);
		if(dfs(h, pp)){
			cout << "escaped\n";
		}else{
			int cur = Find(h, pp);
			if(cur == LLONG_MAX) cout << "oo\n";
			else cout << cur << '\n';
		}
	}
}

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