Submission #958701

#	Time	Username	Problem	Language	Result	Execution time	Memory
958701		YassirSalama	Valley (BOI19_valley)	C++17	36 / 100	3030 ms	40820 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];
int tin[MAXN];
int tout[MAXN];
int t=1;
void dfs(int node,int par=0){
	tin[node]=t++;
	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);
	}
	tout[node]=t++;
}
bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
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(!(is_ancestor(a,r)&&is_ancestor(b,r))){
		cout<<"escaped"<<endl;
		continue;
	}
	int ans=1e18;
	for(auto x:sh){
		int l=LCA(r,x);
		if(is_ancestor(a,r)&&is_ancestor(b,r)&&is_ancestor(l,a)&&is_ancestor(l,b)){
			continue;
		}
		if(is_ancestor(a,x)&&is_ancestor(b,x)&&is_ancestor(l,a)&&is_ancestor(l,b)){
			continue;
		}
		ans=min(ans,depth2[x]+depth2[r]-2*depth2[l]);
	}
	if(ans==1e18){
		cout<<"oo"<<endl;
		continue;
	}
	cout<<ans<<endl;

}

}

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