Submission #952423

#	Time	Username	Problem	Language	Result	Execution time	Memory
952423		RadicaI	Valley (BOI19_valley)	C++17	100 / 100	297 ms	54352 KiB

valley

#include <bits/stdc++.h>
#define int long long
#define pi pair<int,int>
#define pb push_back
#define V vector
#define vi V<int>
#define mi map<int,int>
#define MOD 1000000007
#define MOD2 998244353
#define mp make_pair
#define ins insert
#define qi queue<int>
#define pqi priority_queue<int>
#define si set<int>
#define v2i V<vi>
#define v3i V<v2i>
#define v4i V<v3i>
#define v5i V<v4i>
#define INF 1e18
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define endl "\n"
#define lb lower_bound
#define ub upper_bound
#define print(x) cout << x<<" ";
#define vpi V<pi>
#define Y cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define msi multiset<int>
#define F first
#define S second
#define ld long double
#define RE return;
#define IMP cout<<-1<<endl;return;
using namespace std;

template <typename T>
std::istream& operator>>(std::istream& in, std::vector<T>& vec) {
    for (T& x : vec) {
        in >> x;
    }
    return in;
}
V<vpi> adj;
v2i bin;
v2i bin2;
int n;
vi dist; vi depth;
vi good;
vi best; 
vi val;
const int mx = 17;
void dfs(int node, int x){
	bin[node][0] = x;
	if(good[node]) best[node] = dist[node];
	for(int i=1; i<mx; i++) bin[node][i] = bin[bin[node][i-1]][i-1];
	for(auto &y: adj[node])if(y.F!=x){
		depth[y.F] = depth[node]+1;
		dist[y.F] = dist[node] + y.S;
		dfs(y.F, node);
		best[node] = min(best[node], best[y.F]);
	}
	val[node] = (best[node] == INF ? INF : best[node] - 2*dist[node]);
	bin2[node][0] = val[node];
}

int kth(int x, int k){
	for(int i=0; i<mx; i++)if((1<<i)&k) x = bin[x][i];
	return x;
}
int isAncestor(int a, int anc){
	if(depth[a] <depth[anc] ) return 0;
	else return kth(a, depth[a]-depth[anc]) == anc;
}
int lca(int x, int y){
	if(depth[x]>depth[y]) swap(x,y);
	y = kth(y, depth[y]-depth[x]);
	if(x==y) return x;
	for(int i=mx-1; i>=0; i--){
		if(bin[x][i] != bin[y][i]) x = bin[x][i], y = bin[y][i];
	}
	return bin[x][0];
	
}

signed main(){
	fastio;
	int s,q,e;cin>>n>>s>>q>>e; e--;
	adj.resize(n); bin = v2i(n, vi(mx)); bin2 = v2i(n, vi(mx));
	dist.resize(n,0); depth.resize(n,0); good.resize(n,0); best.resize(n,INF); val.resize(n,INF);
	vpi edgs(n-1);
	for(int i=1; i<n; i++){
		int a,b,w; cin>>a>>b>>w; a--;b--;
		adj[a].pb({b,w});
		adj[b].pb({a,w});
		edgs[i-1] = {a,b};
	}
	for(int i=0; i<s; i++){
		int k; cin >> k; 
		good[k-1]=1;
	}
	dfs(e,e);
	for(auto &x: edgs)if(depth[x.F] > depth[x.S]) swap(x.F,x.S);
	for(int i=1; i<mx; i++)for(int j=0; j<n; j++) bin2[j][i] = min(bin2[j][i-1], bin2[bin[j][i-1]][i-1]);
	while(q--){
		int i,r; cin>>i>>r; i--; r--; 
		int token = edgs[i].S;
		if(!isAncestor(r, token)){
			cout<<"escaped"<<endl;
			continue;
		}
		int jump = depth[r] - depth[token]+1;
		int ans = INF; int prev = dist[r];
		for(int j=0; j<mx; j++)if((1<<j) & jump)  ans = min(ans, bin2[r][j]), r = bin[r][j];
		if(ans==INF) cout<<"oo"<<endl;
		else cout <<ans+prev<<endl;
	}
	
}

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