Submission #723103

#	Time	Username	Problem	Language	Result	Execution time	Memory
723103		PoPularPlusPlus	Valley (BOI19_valley)	C++17	100 / 100	282 ms	58476 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
//const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

bool remender(ll a , ll b){return a%b;}

//freopen("problemname.in", "r", stdin);
//freopen("problemname.out", "w", stdout);

const int N = 100002,L=20;

vector<pair<int,ll>> adj[N];
bool shop[N];
int timer,tin[N],tout[N],up[N][L];
ll sum[N][L],shop_dis[N][L],subtree_dis[N];
ll inf = 100000000000005;

void init(int node , int par){
	subtree_dis[node] = inf;
	if(shop[node])subtree_dis[node] = 0;
	for(auto i : adj[node]){
		if(i.vf != par){
			init(i.vf , node);
			subtree_dis[node] = min(subtree_dis[node] , subtree_dis[i.vf]+i.vs);
		}
	}
}

void dfs(int node , int par , int weight){
	up[node][0] = par;
	tin[node] = timer++;
	sum[node][0] = weight;
	shop_dis[node][0] = subtree_dis[par]+sum[node][0];
	for(int i = 1; i < L; i++){
		up[node][i] = up[up[node][i-1]][i-1];
		shop_dis[node][i] = min(shop_dis[node][i-1],shop_dis[up[node][i-1]][i-1]+sum[node][i-1]);
		sum[node][i] = sum[node][i-1] + sum[up[node][i-1]][i-1];
	}
	for(auto i : adj[node]){
		if(i.vf != par){
			dfs(i.vf , node , i.vs);
		}
	}
	tout[node] = timer++;
}

bool is_lca(int x , int y){
	return tin[x] <= tin[y] && tout[x] >= tout[y];
}

int find(int x , int y){
	if(is_lca(x,y))return x;
	if(is_lca(y,x))return y;
	for(int i = L - 1; i >= 0; i--){
		if(!is_lca(up[x][i],y))x = up[x][i];
	}
	return up[x][0];
}

void solve(){
	int n;
	cin >> n;
	int m;
	cin >> m;
	int q;
	cin >> q;
	int root;
	cin >> root;
	vector<pair<int,int>> edges;
	for(int i = 0; i < n - 1; i++){
		int u , v , w;
		cin >> u >> v >> w;
		adj[u].pb(mp(v,w));
		adj[v].pb(mp(u,w));
		edges.pb(mp(u,v));
	}
	for(int i = 0; i < m; i++){
		int x;
		cin >> x;
		shop[x] = 1;
	}
	init(root,root);
	timer = 0;
	dfs(root,root,0);
	while(q--){
		int index , start;
		cin >> index >> start;
		index--;
		int a = edges[index].vf , b = edges[index].vs;
		if(!is_lca(a,b)){
			swap(a,b);
		}
		if(is_lca(b,start)){
			ll ans = subtree_dis[start];
			ll s = 0;
			for(int i = L-1; i >= 0; i--){
				if(is_lca(b,up[start][i])){
					ans = min(ans , shop_dis[start][i]+s);
					s += sum[start][i];
					start = up[start][i];
				}
			}
			if(ans >= inf){
				cout << "oo\n";
			}
			else cout << ans << '\n';
		}
		else {
			cout << "escaped\n";
		}
	}
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
   // int t;cin>>t;
   // while(t--){
		solve();
	//}
	return 0;
}

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