Submission #1200919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200919		PlayVoltz	Valley (BOI19_valley)	C++20	100 / 100	1740 ms	240772 KiB

valley

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

struct ooga{
	int s, e, m, val;
	ooga *l, *r;
	
	ooga(int S, int E){
		s = S, e = E, m = (s+e)/2;
		val=LLONG_MAX/2;
		if (s!=e){
			l = new ooga(s, m);
			r = new ooga(m+1, e);
		}
	}
	void up(int ind, int nv){
		if (s==e)val=nv;
		else{
			if (ind<=m)l->up(ind, nv);
			else r->up(ind, nv);
			val = min(l->val, r->val);
		}
	}
	int query(int left, int right){
		if (s==left && e==right)return val;
		if (right<=m)return l->query(left, right);
		else if (left>m)return r->query(left, right);
		else return min(l->query(left, m), r->query(m+1, right));
	}
}*st[100005];

int counter=0, depth[100005], dist[100005], in[100005], out[100005], par[100005], sz[100005], twok[100005][18];
vector<int> temp, inside[100005], lvl;
vector<pii> graph[100005];

void dfs(int node, int p, int dep, int d){
	in[node]=++counter;
	depth[node]=dep;
	dist[node]=d;
	twok[node][0]=p;
	for (int i=1; i<18; ++i)twok[node][i]=twok[twok[node][i-1]][i-1];
	for (auto num:graph[node])if (num.fi!=p)dfs(num.fi, node, dep+1, d+num.se);
	out[node]=counter;
}

int kth(int a, int k){
	for (int i=0; i<18; ++i)if (k&(1<<i))a=twok[a][i];
	return a;
}

int lca(int a, int b){
	if (depth[a]<depth[b])swap(a, b);
	a=kth(a, depth[a]-depth[b]);
	if (a==b)return a;
	for (int i=17; i>=0; --i)if (twok[a][i]!=twok[b][i])a=twok[a][i], b=twok[b][i];
	return twok[a][0];
}

int calc(int a, int b){
	return dist[a]+dist[b]-2*dist[lca(a, b)];
}

int dfs_size(int node, int p){
	temp.pb(in[node]);
	sz[node]=1;
	for (auto num:graph[node])if (num.fi!=p&&lvl[num.fi]==-1)sz[node]+=dfs_size(num.fi, node);
	return sz[node];
}

int centroidfind(int node, int p, int size){
	for (auto num:graph[node])if (num.fi!=p&&lvl[num.fi]==-1&&sz[num.fi]>size/2)return centroidfind(num.fi, node, size);
	return node;
}

void build(int node, int p, int d){
	temp.clear();
	int c=centroidfind(node, p, dfs_size(node, p));
	lvl[c]=d;
	par[c]=p;
	sort(temp.begin(), temp.end());
	inside[c]=temp;
	st[c] = new ooga(0, temp.size()-1);
	for (auto num:graph[c])if (lvl[num.fi]==-1)build(num.fi, c, d+1);
}

void cupdate(int node){
	for (int c=node; c!=-1; c=par[c])st[c]->up((lower_bound(inside[c].begin(), inside[c].end(), in[node])-inside[c].begin()), calc(node, c));
}

int cquery(int node, int a){
	int res=LLONG_MAX/2;
	for (int c=node; c!=-1; c=par[c]){
		int low=(lower_bound(inside[c].begin(), inside[c].end(), in[a])-inside[c].begin());
		int high=(upper_bound(inside[c].begin(), inside[c].end(), out[a])-inside[c].begin())-1;
		if (low<=high)res=min(res, calc(c, node)+st[c]->query(low, high));
	}
	return res;
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, s, q, e, a, b, c;
	cin>>n>>s>>q>>e;
	pii edges[n+5];
	lvl.resize(n+1, -1);
	for (int i=1; i<n; ++i){
		cin>>a>>b>>c;
		graph[a].pb(mp(b, c));
		graph[b].pb(mp(a, c));
		edges[i]=mp(a, b);
	}
	dfs(e, e, 0, 0);
	build(e, -1, 0);
	while (s--)cin>>a, cupdate(a);
	while (q--){
		cin>>a>>b;
		if (in[edges[a].fi]>in[edges[a].se])c=edges[a].fi;
		else c=edges[a].se;
		if (in[c]<=in[b]&&in[b]<=out[c]){
			int res=cquery(b, c);
			if (res==LLONG_MAX/2)cout<<"oo\n";
			else cout<<res<<"\n";
		}
		else cout<<"escaped\n";
	}
}

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