Submission #1269875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269875		namhh	Valley (BOI19_valley)	C++20	100 / 100	167 ms	47280 KiB

valley

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e5+5;
const int lg = 17;
int n,s,q,e,st[N][lg],sta[N],ed[N],dp[N],emilia[N][lg],a[N],h[N],check[N],d[N],timer = 1;
vector<pii>adj[N];
struct edges{
	int u,v,c;
};
edges rem[N];
void dfs(int u, int p, int c){
	st[u][0] = p;
	h[u] = h[p]+1;
	sta[u] = timer;
	timer++;
	for(int i = 1; i < lg; i++) st[u][i] = st[st[u][i-1]][i-1];
	for(auto[v,w]: adj[u]){
		if(v != p){
			d[v] = d[u]+w;
			dfs(v,u,c+w);
			dp[u] = min(dp[u],dp[v]+w);
		}
	}
	if(check[u]) dp[u] = 0;
	ed[u] = timer-1;
}
void build(){
	for(int j = 1; j < lg; j++){
		for(int i = 1; i <= n; i++) emilia[i][j] = 1e18;
	}
	for(int i = 1; i <= n; i++) emilia[i][0] = dp[i];
	for(int j = 1; j < lg; j++){
		for(int i = 1; i <= n; i++) emilia[i][j] = min(emilia[i][j-1],emilia[st[i][j-1]][j-1]);
	}
}
int get(int u, int v){
	//cout << u << " " << v << "\n";
	int ans = 1e18;
	for(int i = lg-1; i >= 0; i--){
		//if(u == 5 && i == 1 && v == 1) cout << h[st[u][i]] << " " << h[v] << "\n";
		if(h[st[u][i]] >= h[v]){
			ans = min(ans,emilia[u][i]);
			//cout << u << " " << i << " " << ans << "\n";
			u = st[u][i];
		}
	}
	return ans;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> s >> q >> e;
	for(int i = 1; i < n; i++){
		int u,v,c;
		cin >> u >> v >> c;
		adj[u].push_back({v,c});
		adj[v].push_back({u,c});
	    emilia[i][0] = 1e18;
		dp[i] = 1e18;
		rem[i] = {u,v,c};
	}
	for(int i = 1; i <= n; i++){
		emilia[i][0] = 1e18;
		dp[i] = 1e18;
	}
	for(int i = 1; i <= s; i++){
		cin >> a[i];
		check[a[i]] = 1;
	}
	dfs(e,0,0);
	for(int i = 1; i <= n; i++) dp[i] -= d[i];
	build();
	//cout << st[5][1] << "\n";
	while(q--){
		int cam,cur;
		cin >> cam >> cur;
		int u = rem[cam].u;
		int v = rem[cam].v;
		int dm = u;
		if(st[v][0] == u) dm = v;
		if(sta[dm] <= sta[cur] && sta[cur] <= ed[dm]){
			if(dm == u) dm = v;
			else dm = u;
			int x = get(cur,dm)+d[cur];
			//cout << cur << " " << dm << " " << get(cur,dm) << " ";
			if(x > 1e17) cout << "oo" << "\n";
			else cout << x << "\n";
		}
		else cout << "escaped" << "\n";
	}
}
//-----+--+----+-==-=*==--=+----------==----------------+=-----==-=+-==----------------
//---===+=----+=----=*=+=*+----------==-----------+=-----==-----==--+-+----------------
//---+=**=-=+---------***+----=------=-------------=-------+-----==-+--=---------------
//----*+-+++**++------=#+----===-----=-------------=-------==-----+-=+=-+--------------
//----++#***+*+++-----=+-----=-=----+---------------+-------+=-----*=-==-+-------------
//---+=+**++**++++==++*=-----===----+---------------+----=---=-----=*+*=-==------------
//---++**==+--++++++***-----+-+-----+---------------==---==--==-----+**---+------------
//----++*#=-+++***+***------+-+-----+----------------=----+---*+=---=*#=-=-+-----------
//-----=**+++*+++**%++-----=--+-----+----------------=----*=--==+==++***-=+==----------
//-------**#**++*%%@==-----=--+-----+-------------=+++++=-+=---+=+=-=+**--+++----------
//---------====+@@%@-=-----+--+--=+++++--------------=----+==--===---+*---+==+---------
//-----------=@*%%%%-=-----+=-==-----=---------------=----+--=-==+-=-=*----++==--------
//----------%#=%=#%%==-----=+--=-----=---------------+----+--===*=*==**=---+-++--------
//--------+@++@=*@%*-=-----=+=-=-----==-------------++-*%%%***=++-+=-+-+---=-===-------
//-------#%-=%=+@%@+-=-----=+=--+++*==*=------------**@*##%*--=-+-----=+---==-+==------
//------=%+-=%=%*@@--=-----=*#*=+*###@%*---------=+*++%***##=-+-+------+---==-=+=------
//-------%*-=%@+@@+-*=-----+-=--@##*##=+==----------=-#*#***-==-+------+---==--++------
//-------+@=+@@*@*-=-=-----=-==-*#%*##=----------------++=+=----+------+---==--==+-----
//--------%@@%%@*=--+=-----=---+=+#==*-------------------==-----+------+---==---=+-----
//----------%+=#-=--==-----+-------===--------------------------*------+---==---+==----
//---------##-%+-=---=-----++----------------------------------=*------=---==---=+=----
//--------=#-*@=-=---=-----**=----------------=----------------+*------=---==----++----
//-------=@==%*-==---=-----++*---------------------------------*+------+---==----++=---
//------=%*-=@--==---=-----+++*-------------------------------**=------+---==----==+---
//------*#--##--==---=-----+++*+--------------------+--------+**=------+---=-----==+---
//-----=@=--@*---=---=-----+++#+*=--------=+=----=+=-------=#+**-------+---+-----==+---
//----=%+--=@+---=---=-----=+**++**=---------------------=*+****------==---+-----===---
//----*#---*@=---=--==-----=*+#++*+++*=---------------=*#*++#+*+==----+==-+=-----====--
//---=@=---%%----=--=+-----=*+#++*++++***+----------*****+++#**++-----+==-+-------===--
//---%#----%%---==--=+------*+*++*++**+***+**++=+****+==++*+**#-+-----+==-+-------+==--
//--=@=---=%#---==--+*------*++*+*++#+*****++++****+--==*=*****==----===-==-------+==--
//--##----=@*---+=--+*------=++*+*++*++++++*******=-------+***==-----===-==-------+==--
//-=@+----+@=---+=--+#=-----=*+*+*++#++*+++**#*++-+-------+***-+-----+===+--------*==--
//-*@=----*@=---=---+*+------++*+*+*-=++*+***=-+--+--------#**-=-----*====--------*==--
//=%%-----#@---==---=**------++****---------*=----+--------=#=+-----=*==*---------*==--
//=@*-----%@---==---=*#------++*+------=+%@##@+==%%+*+==----+==-----+*+-++++=+++*++==--

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