Submission #496454

#	Time	Username	Problem	Language	Result	Execution time	Memory
496454		Ierus	Valley (BOI19_valley)	C++17	23 / 100	208 ms	34036 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;
}
const int LG = 19;
int up[N][LG+2], tin[N], tout[N], timer;
void dfs1(int v, int p = 0) {
	tin[v] = ++timer;
	up[v][0] = p;
	for (int i = 1; i <= LG; ++i)
		up[v][i] = up[up[v][i-1]][i-1];
	for (auto to : g[v]) {
		if (to.v != p)
			dfs1(to.v, v);
	}
	tout[v] = timer;
}
bool upper(int a, int b) {
	return tin[a] <= tin[b] && tout[b] <= tout[a] ;
}
int lca (int a, int b) {
	if (upper (a, b))  return a;
	if (upper (b, a))  return b;
	for (int i = LG; i>=0; --i)
		if (!upper(up[a][i], b))
			a = up[a][i];
	return up[a][0];
}
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;
	}
//	if(n <= 1000 && q <= 10000){
//		for(int i = 1; i <= q; ++i){
//			int pp, h;
//			cin >> pp >> h;
//			used.reset();
//			if(dfs(h, pp)){
//				cout << "escaped\n";
//			}else{
//				int cur = Find(h, pp);
//				if(cur == LLONG_MAX) cout << "oo\n";
//				else cout << cur << '\n';
//			}
//		}
//		exit(false);
//	}
	dfs1(1, 1);
	for(int i = 1; i <= q; ++i){
		int pp, h;
		cin >> pp >> h;
		int lc = lca(h, e);
		if((lca(e, x[pp]) == x[pp]  && lca(x[pp], lc) == lc) && (lca(e, y[pp]) == y[pp]  && lca(y[pp], lc) == lc)){
			cout << "0\n";
			continue;
		}
		if((lca(h, x[pp]) == x[pp]  && lca(x[pp], lc) == lc) && (lca(h, y[pp]) == y[pp]  && lca(y[pp], lc) == lc)){
			cout << "0\n";
			continue;
		}
		cout << "escaped\n";
	}
}
/*
	10 10 5 4
7 2 3
4 8 3
9 10 1
6 7 3
9 2 3
10 1 2
8 2 2
5 2 1
3 8 2
1 2 3 4 5 6 7 8 9 10
2 1
1 5
8 4
6 2
7 7

*/

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