Submission #261445

#	Time	Username	Problem	Language	Result	Execution time	Memory
261445		CSQ31	Valley (BOI19_valley)	C++14	100 / 100	236 ms	49148 KiB

valley

#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
int gcd(int A,int B) {if(!B)return A;return gcd(B,A%B);}
const int MAXN = 1e5+5;
ll n,s,q,e;
vector<vector<PII>> adj(MAXN);
vector<bool>shop(MAXN,0);
ll par[21][MAXN];
ll mn[21][MAXN];
ll sub[MAXN];
ll depth[MAXN];
ll depthw[MAXN];
ll tin[MAXN];
ll tout[MAXN];
ll timer = 0;
void dfs(int v,int u = 0)
{
	sub[v] = INF;
	if(shop[v])sub[v] = depthw[v];
	tin[v] = ++timer;
	for(auto x:adj[v]){
		int to = x.fi;
		ll w = x.se;
		if(to == u)continue;
		depth[to] = depth[v]+1;
		depthw[to] = depthw[v]+w;
		dfs(to,v);
		sub[v] = min(sub[v],sub[to]);
	}
	tout[v] = timer;
	par[0][v] = u;
	if(sub[v] == INF)mn[0][v] = INF;
	else mn[0][v] = sub[v]-2*depthw[v];
}
bool chk(int v,int u)
{
	return (tin[v] >= tin[u] && tout[u] >= tout[v]);
}
ll query(int blk,int v)
{
	int tmp = depth[v]-depth[blk]+1;
	ll ans = INF;
	for(int j=0;tmp;j++,tmp>>=1){
		if(tmp&1){
			ans = min(ans,mn[j][v]);
			v = par[j][v];
		}
	}
	return ans;
}
int main()
{
	owo
	cin>>n>>s>>q>>e;
	vector<pii>edge(n+1);
	for(int i=1;i<n;i++){
		ll v,u,w;
		cin>>v>>u>>w;
		adj[v].pb({u,w});
		adj[u].pb({v,w});
		edge[i] = {v,u};
	}
	while(s--){
		int c;cin>>c;
		shop[c] = 1;
	}
	dfs(e);
	for(int i=1;i<n;i++){
		int v = edge[i].fi;
		int u = edge[i].se;
		if(depth[u] > depth[v])swap(v,u);
		edge[i] = {v,u};
	}
	for(int k=1;k<=20;k++){
		for(int i=1;i<=n;i++){
			int jump = par[k-1][i];
			par[k][i] = par[k-1][jump];
			mn[k][i] = min(mn[k-1][i],mn[k-1][jump]);
		}
	}
	while(q--){
		int i,r;
		cin>>i>>r;
		int v = edge[i].fi;
		if(!chk(r,v))cout<<"escaped"<<'\n';
		else{
			ll ans = query(v,r);
			if(ans >= INF)cout<<"oo"<<'\n';
			else cout<<ans+depthw[r]<<'\n';
			
		}
	}
	
}
	

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