Submission #535104

#	Time	Username	Problem	Language	Result	Execution time	Memory
535104		new_acc	Valley (BOI19_valley)	C++14	100 / 100	354 ms	46948 KiB

valley

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e5+10;
const ll INF=1e18;
ll dp[N],g[N];
ll odl[N];
int jump[N][20],dep[N];
bitset<N>sk;
vector<pair<int,int> > zap[N];
ll res[N],mini[N][20];
vector<pair<pair<int,int>,int> > graf[N];
void dfs(int v,int o,ll xd){
	odl[v]=xd;
	if(sk[v]) dp[v]=0;
	else dp[v]=INF;
	for(auto [x,num]:graf[v]){
		int u=x.fi,c=x.se;
		if(o==u) continue;
		dep[u]=dep[v]+1;
		dfs(u,v,xd+(ll)c);
		dp[v]=min(dp[u]+(ll)c,dp[v]);
	}
}
ll zmini(int v,int d){
	ll res=(dp[v]==INF?INF:dp[v]-odl[v]);
	for(int i=18;i>=0;i--)
		if(dep[jump[v][i]]>=d) res=min(res,mini[v][i]),v=jump[v][i];
	return res;
}
void dfs2(int v,int o){
	jump[v][0]=o,mini[v][0]=min((dp[v]==INF?INF:dp[v]-odl[v]),(dp[o]==INF?INF:dp[o]-odl[o]));
	for(int i=1;i<=18;i++) jump[v][i]=jump[jump[v][i-1]][i-1],mini[v][i]=min(mini[v][i-1],mini[jump[v][i-1]][i-1]);
	for(auto [x,num]:graf[v]){
		int u=x.fi,c=x.se;
		if(o==u) continue;
		g[num]=dep[u];
		dfs2(u,v);
		g[num]=-1;
	}
	for(auto [num,i]:zap[v]){
		if(g[num]==-1) res[i]=-11;
		else{
			ll pom=zmini(v,g[num]);
			if(pom==INF) res[i]=-1;
			else res[i]=pom+odl[v];
		}
	}
}
void solve(){
	int n,s,q,e;
	cin>>n>>s>>q>>e;
	for(int i=1;i<n;i++){
		int a,b,c;
		cin>>a>>b>>c;
		graf[a].push_back({{b,c},i}),graf[b].push_back({{a,c},i});
	}
	for(int i=1;i<=s;i++){
		int a;
		cin>>a;
		sk[a]=1;
	}
	for(int i=1;i<=q;i++){
		int a,b;
		cin>>b>>a;
		zap[a].push_back({b,i});
	}
	for(int i=1;i<=n;i++) g[i]=-1;
	dfs(e,e,0);	
	dfs2(e,e);
	for(int i=1;i<=q;i++){
		if(res[i]==-11) cout<<"escaped\n";
		else{
			if(res[i]==-1) cout<<"oo\n";
			else cout<<res[i]<<"\n";
		}
	}
}
int main(){
	solve();
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(int, int, ll)':
valley.cpp:21:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |  for(auto [x,num]:graf[v]){
      |           ^
valley.cpp: In function 'void dfs2(int, int)':
valley.cpp:38:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |  for(auto [x,num]:graf[v]){
      |           ^
valley.cpp:39:14: warning: unused variable 'c' [-Wunused-variable]
   39 |   int u=x.fi,c=x.se;
      |              ^
valley.cpp:45:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |  for(auto [num,i]:zap[v]){
      |           ^

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