Submission #217484

#	Time	Username	Problem	Language	Result	Execution time	Memory
217484		MohamedAhmed04	Valley (BOI19_valley)	C++14	100 / 100	309 ms	27388 KiB

valley

#include <bits/stdc++.h>

using namespace std ;

const long long inf = -1e15 ;
const int MAX = 1e5 + 10 ;

long long tree[4 * MAX] , lazy[4 * MAX] ;

void prop(int node , int l , int r)
{
	tree[node] += lazy[node] ;
	if(l != r)
	{
		lazy[node << 1] += lazy[node] ;
		lazy[node << 1 | 1] += lazy[node] ;
	}
	lazy[node] = 0 ;
	return ;
}

long long Merge(long long a , long long b)
{
	if(a < 0)
		return b ;
	if(b < 0)
		return a ;
	return min(a , b) ;
}

void update(int node , int l , int r , int from , int to , long long val)
{
	prop(node , l , r) ;
	if(from > r || to < l)
		return ;
	if(l >= from && r <= to)
	{
		lazy[node] += val ;
		prop(node , l , r) ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	update(node << 1 , l , mid , from , to , val) ;
	update(node << 1 | 1 , mid+1 , r , from , to , val) ;
	tree[node] = Merge(tree[node << 1] , tree[node << 1 | 1]) ;
}

long long query(int node , int l , int r , int from , int to)
{
	prop(node , l , r) ;
	if(from > r || to < l || from > to)
		return -1 ;
	if(l >= from && r <= to)
		return tree[node] ;
	int mid = (l + r) >> 1 ;
	long long a = query(node << 1 , l , mid , from , to) ;
	long long b = query(node << 1 | 1 , mid+1 , r , from , to) ;
	return Merge(a , b) ;
}

int u[MAX] , v[MAX] , c[MAX] , mark[MAX] , in[MAX] , out[MAX] ;
int n , s , q , e ;

long long ans[MAX] ;

vector< vector< pair<int , int> > >adj(MAX) , Query(MAX) ;

int tim = 0 ;

void dfs1(int node , int par , long long dist)
{
	in[node] = ++tim ;
	if(mark[node])
		update(1 , 1 , n , in[node] , in[node] , dist) ;
	else
		update(1 , 1 , n , in[node] , in[node] , inf) ;
	for(auto &child : adj[node])
	{
		if(child.first == par)
			continue ;
		dfs1(child.first , node , dist+child.second) ;
	}
	out[node] = tim ;
	return ;
}

void dfs2(int node , int par)
{
	for(auto &i : Query[node])
	{
		int x = i.first ;
		bool flag1 = (in[node] >= in[v[x]] && in[node] <= out[v[x]]) ;
		bool flag2 = (in[e] >= in[v[x]] && in[e] <= out[v[x]]) ;
		if(flag1 == flag2)
		{
			ans[i.second] = -2 ;
			continue ;
		}
		if(flag1)
		{
			ans[i.second] = query(1 , 1 , n , in[v[x]] , out[v[x]]) ;
			if(ans[i.second] < 0)
				ans[i.second] = -1 ;
		}
		else
		{
			long long a = query(1 , 1 , n , 1 , in[v[x]]-1) ;
			long long b = query(1 , 1 , n  , out[v[x]]+1 , n) ;
			ans[i.second] = Merge(a , b) ;
			if(ans[i.second] < 0)
				ans[i.second] = -1 ;
		}
	}
	for(auto &child : adj[node])
	{
		if(child.first == par)
			continue ;
		update(1 , 1 , n , 1 , n , child.second) ;
		update(1 , 1 , n , in[child.first] , out[child.first] , -2ll * child.second) ;
		dfs2(child.first , node) ;
		update(1 , 1 , n , 1 , n , -1ll * child.second) ;
		update(1 , 1 , n , in[child.first] , out[child.first] , 2ll * child.second) ;
	}
	return ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>s>>q>>e ;
	for(int i = 1 ; i <= n-1 ; ++i)
	{
		cin>>u[i]>>v[i]>>c[i] ;
		adj[u[i]].emplace_back(v[i] , c[i]) ;
		adj[v[i]].emplace_back(u[i] , c[i]) ;
	}
	for(int i = 0 ; i < s ; ++i)
	{
		int x ;
		cin>>x ;
		mark[x] = 1 ;
	}
	for(int i = 0 ; i < q ; ++i)
	{
		int x , y ;
		cin>>x>>y ;
		Query[y].emplace_back(x , i) ;
	}
	dfs1(1 , -1 , 0) ;
	for(int i = 1 ; i <= n-1 ; ++i)
	{
		if(in[v[i]] < in[u[i]])
			swap(u[i] , v[i]) ;
	}
	dfs2(1 , -1) ;
	for(int i = 0 ; i < q ; ++i)
	{
		if(ans[i] >= 0)
			cout<<ans[i]<<"\n" ;
		else if(ans[i] == -1)
			cout<<"oo\n" ;
		else
			cout<<"escaped\n" ;
	}
	return 0 ;
}		

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