oj.uz

Submission #655240

# Submission time Handle Problem Language Result Execution time Memory
655240 2022-11-03T15:26:17 Z inksamurai Valley (BOI19_valley) C++17
100 / 100
 282 ms 70984 KB 
#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3U2xVYR ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

const int inf=1e17;

struct E{
	int to,w,id;
	E(int _to=0,int _w=0,int _id=0):
	to(_to),
	w(_w),
	id(_id){}
};

void chmin(int&a,int b){
	a=min(a,b);
}

signed main(){
_3U2xVYR;
	int n,k,q,rt;
	cin>>n>>k>>q>>rt;
	rt-=1;
	vec(pii) es;
	vec(vec(E)) adj(n);
	rep(i,n-1){
		int u,v,w;
		cin>>u>>v>>w;
		u-=1,v-=1;
		es.pb(pii(u,v));
		adj[u].pb(E(v,w,i));
		adj[v].pb(E(u,w,i));
	}
	vi rbe(n);
	rep(i,k){
		int v;
		cin>>v;
		v-=1;
		rbe[v]=1;
	}
	vec(vec(pii)) qry(n);
	rep(_,q){
		int id,v;
		cin>>id>>v;
		id-=1,v-=1;
		qry[v].pb(pii(id,_));
	}
	
	vi par(n,rt);
	vi dpth(n,0);
	vi qs(n,inf);
	auto dfs=[&](auto self,int v)->void{
		if(rbe[v]) qs[v]=dpth[v];
		for(auto [to,w,id]:adj[v]){
			if(to==par[v]) continue;
			par[to]=v;
			dpth[to]=dpth[v]+w;
			self(self,to);
			chmin(qs[v],qs[to]);
		}
	};
	dpth[rt]=0;
	dfs(dfs,rt);
	
	vec(vi) spr(20,vi(n,rt)); // everyone goes to rt
	vec(vi) dp(20,vi(n,inf));
	rep(i,n){
		spr[0][i]=par[i];
		chmin(dp[0][i],qs[i]-2*dpth[i]);
		chmin(dp[0][i],qs[par[i]]-2*dpth[par[i]]);
	}
	rng(j,1,20){
		rep(i,n){
			int up=spr[j-1][i];
			spr[j][i]=spr[j-1][up];
			chmin(dp[j][i],dp[j-1][i]);
			chmin(dp[j][i],dp[j-1][up]);
		}
	}

	auto eval=[&](int s,int v)->int{
		int res=inf;
		per(j,20){
			int up=spr[j][v];
			if(dpth[up]>dpth[s]){
				// print("go",up);
				chmin(res,dp[j][v]);
				v=up;
			}
		}
		return res;
	};

	vi pns(q,inf);
	set<int> st;
	auto rfs=[&](auto self,int v)->void{
		for(auto p:qry[v]){
			int id=p.fi;
			// print(id,v);
			if(st.find(id)==st.end()){
				pns[p.se]=-1;
			}else{
				int s=es[id].fi;
				if(dpth[s]>dpth[es[id].se]){
					s=es[id].se;
				}
				pns[p.se]=eval(s,v); // don't forget pencakes
				pns[p.se]+=dpth[v];
				// print(qs[v]);
				chmin(pns[p.se],qs[v]-dpth[v]);
			}
		}
		for(auto [to,w,id]:adj[v]){
			if(to==par[v]) continue;
			st.insert(id);
			self(self,to);
			st.erase(st.find(id));
		}
	};
	rfs(rfs,rt);

	rep(i,q){
		int ans=pns[i];
		if(ans<0){
			cout<<"escaped\n";
		}else if(ans>1e14){
			cout<<"oo\n";
		}else{
			cout<<ans<<"\n";
		}
	}
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 3 ms 812 KB Output is correct
3 Correct 3 ms 848 KB Output is correct
4 Correct 3 ms 724 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 3 ms 812 KB Output is correct
3 Correct 3 ms 848 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 840 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 2 ms 796 KB Output is correct
13 Correct 2 ms 852 KB Output is correct
14 Correct 2 ms 844 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 51496 KB Output is correct
2 Correct 184 ms 55232 KB Output is correct
3 Correct 205 ms 55456 KB Output is correct
4 Correct 247 ms 61628 KB Output is correct
5 Correct 192 ms 61192 KB Output is correct
6 Correct 282 ms 69084 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 3 ms 812 KB Output is correct
3 Correct 3 ms 848 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 840 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 2 ms 796 KB Output is correct
13 Correct 2 ms 852 KB Output is correct
14 Correct 2 ms 844 KB Output is correct
15 Correct 173 ms 51496 KB Output is correct
16 Correct 184 ms 55232 KB Output is correct
17 Correct 205 ms 55456 KB Output is correct
18 Correct 247 ms 61628 KB Output is correct
19 Correct 192 ms 61192 KB Output is correct
20 Correct 282 ms 69084 KB Output is correct
21 Correct 161 ms 54832 KB Output is correct
22 Correct 174 ms 54716 KB Output is correct
23 Correct 187 ms 54948 KB Output is correct
24 Correct 224 ms 61920 KB Output is correct
25 Correct 245 ms 70984 KB Output is correct
26 Correct 166 ms 54832 KB Output is correct
27 Correct 176 ms 54792 KB Output is correct
28 Correct 196 ms 54908 KB Output is correct
29 Correct 218 ms 59356 KB Output is correct
30 Correct 244 ms 64188 KB Output is correct
31 Correct 158 ms 54900 KB Output is correct
32 Correct 171 ms 54836 KB Output is correct
33 Correct 180 ms 55072 KB Output is correct
34 Correct 257 ms 61148 KB Output is correct
35 Correct 244 ms 70768 KB Output is correct
36 Correct 217 ms 61504 KB Output is correct