oj.uz

Submission #958701

# Submission time Handle Problem Language Result Execution time Memory
958701 2024-04-06T11:51:36 Z YassirSalama Valley (BOI19_valley) C++17
36 / 100
 3000 ms 40820 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10588 KB Output is correct
2 Correct 7 ms 10588 KB Output is correct
3 Correct 14 ms 10852 KB Output is correct
4 Correct 24 ms 10844 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10588 KB Output is correct
2 Correct 7 ms 10588 KB Output is correct
3 Correct 14 ms 10852 KB Output is correct
4 Correct 24 ms 10844 KB Output is correct
5 Correct 3 ms 10840 KB Output is correct
6 Correct 4 ms 10852 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 8 ms 10884 KB Output is correct
9 Correct 8 ms 10884 KB Output is correct
10 Correct 8 ms 10856 KB Output is correct
11 Correct 54 ms 10896 KB Output is correct
12 Correct 55 ms 10844 KB Output is correct
13 Correct 14 ms 10840 KB Output is correct
14 Correct 11 ms 10844 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3030 ms 40820 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10588 KB Output is correct
2 Correct 7 ms 10588 KB Output is correct
3 Correct 14 ms 10852 KB Output is correct
4 Correct 24 ms 10844 KB Output is correct
5 Correct 3 ms 10840 KB Output is correct
6 Correct 4 ms 10852 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 8 ms 10884 KB Output is correct
9 Correct 8 ms 10884 KB Output is correct
10 Correct 8 ms 10856 KB Output is correct
11 Correct 54 ms 10896 KB Output is correct
12 Correct 55 ms 10844 KB Output is correct
13 Correct 14 ms 10840 KB Output is correct
14 Correct 11 ms 10844 KB Output is correct
15 Execution timed out 3030 ms 40820 KB Time limit exceeded
16 Halted 0 ms 0 KB -