Submission #958700

#	Time	Username	Problem	Language	Result	Execution time	Memory
958700		YassirSalama	Valley (BOI19_valley)	C++17	0 / 100	3009 ms	39936 KiB

valley

#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
#ifdef IOI
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define int long long
const int MAXN=2e5+100;
const int LOGN=20;
int up[MAXN][LOGN+1];
vector<pair<int,int>> v[MAXN];
vector<vector<int>> ed;
int depth1[MAXN];
int depth2[MAXN];
void dfs(int node,int par=0){
	depth1[node]=depth1[par]+1;
	up[node][0]=par;
	for(int i=1;i<=LOGN;i++) 
		up[node][i]=up[up[node][i-1]][i-1];
	for(auto x:v[node]){
		if(x.F==par) continue;
		depth2[x.F]=depth2[node]+x.S;
		dfs(x.F,node);
	}
}
int LCA(int a,int b){
	if(depth1[a]<depth1[b]) swap(a,b);
	int d=depth1[a]-depth1[b];
	for(int i=LOGN;i>=0;i--){
		if((1LL<<i)&d){
			a=up[a][i];
		}
	}
	if(a==b) return a;
	for(int i=LOGN;i>=0;i--){
		if(up[a][i]!=up[b][i]){
			a=up[a][i];
			b=up[b][i];
		}
	}
	return up[a][0];
}
vector<int> sh;
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n,s,q,e;
cin>>n>>s>>q>>e;
for(int i=1;i<n;i++){
	int a,b;
	int c;
	cin>>a>>b>>c;
	ed.pb({a,b});
	v[a].pb(make_pair(b,c));
	v[b].pb(make_pair(a,c));
}
dfs(e);
for(int i=0;i<s;i++){
	int sx;
	cin>>sx;
	sh.pb(sx);
}
for(int i=0;i<q;i++){
	int p,r;
	cin>>p>>r;
	p--;
	int a=ed[p][0],b=ed[p][1];
	// dbg(a,b,LCA(r,a),LCA(r,b))
	if(!(LCA(r,a)==a&&LCA(r,b)==b)){
		cout<<"escaped"<<endl;
		continue;
	}
	int ans=1e9;
	for(auto x:sh){
		int l=LCA(r,x);
		if((LCA(r,a)==a&&LCA(r,b)==b)&&LCA(a,l)==l&&LCA(b,l)==l) continue;
		if((LCA(x,a)==a&&LCA(x,b)==b)&&LCA(a,l)==l&&LCA(b,l)==l) continue;
		ans=min(ans,depth2[r]+depth2[x]-2*depth2[l]);
	}
	if(ans==1e9){
		cout<<"oo"<<endl;
		continue;
	}
	cout<<ans<<endl;

}

}

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