oj.uz

Submission #246734

# Submission time Handle Problem Language Result Execution time Memory
246734 2020-07-10T04:11:41 Z MohamedAhmed04 Transport (COCI19_transport) C++14
130 / 130
 895 ms 30072 KB 
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std ;
using namespace __gnu_pbds;

template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update> ;

const int MAX = 1e5 + 10 ;

int arr[MAX] , sz[MAX] , mark[MAX] ;
int n ;

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

//centroid decomposition

void dfs(int node , int par)
{
	sz[node] = 1 ;
	for(auto &child : adj[node])
	{
		if(child.first == par || mark[child.first])
			continue ;
		dfs(child.first , node) ;
		sz[node] += sz[child.first] ;
	}
}

int Findcentroid(int node , int par , int sub_sz)
{
	for(auto &child : adj[node])
	{
		if(mark[child.first] || child.first == par)
			continue ;
		if(sz[child.first] > sub_sz / 2)
			return Findcentroid(child.first , node , sub_sz) ;
	}
	return node ;
}

ordered_set< pair<long long , int> >s[MAX] ;

long long ans = 0ll ;

int centroid ;

bool flag ;

void Insert(int node , int par , long long x , long long Min)
{
	Min = min(Min , x) ;
	if(Min >= 0)
		ans += flag ;
	s[centroid].insert({Min * -1ll , node}) ;
	for(auto &child : adj[node])
	{
		if(child.first == par || mark[child.first])
			continue ;
		Insert(child.first , node , x + arr[node] - child.second , Min) ;
	}
}

void Query(int node , int par , long long sum , long long Min)
{
	if(Min >= 0)
		ans += s[centroid].order_of_key({sum+1 , -1}) , ans += flag ;
	for(auto &child : adj[node])
	{
		if(child.first == par || mark[child.first])
			continue ;
		long long x = arr[child.first] - child.second ;
		Query(child.first , node , sum + x , min(Min + x , x)) ;
	}
}

void solve()
{
	flag = true ;
	for(auto &child : adj[centroid])
	{
		if(mark[child.first])
			continue ;
		Query(child.first , -1 , arr[child.first] - child.second , arr[child.first] - child.second) ;
		Insert(child.first , -1 , arr[centroid] - child.second , 0) ;
	}
	s[centroid].clear() ;
	reverse(adj[centroid].begin() , adj[centroid].end()) ;
	flag = false ;
	for(auto &child : adj[centroid])
	{
		if(mark[child.first])
			continue ;
		Query(child.first , -1 , arr[child.first] - child.second , arr[child.first] - child.second) ;
		Insert(child.first , -1 , arr[centroid] - child.second , 0) ;
	}
	s[centroid].clear() ;
}

void build(int node)
{
	dfs(node , -1) ;
	centroid = Findcentroid(node , -1 , sz[node]) ;
	mark[centroid] = 1 ;
	solve() ;
	for(auto &child : adj[centroid])
	{
		if(!mark[child.first])
			build(child.first) ;
	}
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] ;
	for(int i = 0 ; i < n-1 ; ++i)
	{
		int x , y , z ;
		cin>>x>>y>>z ;
		adj[x].push_back({y , z}) ;
		adj[y].push_back({x , z}) ;
	}
	build(1) ;
	return cout<<ans<<"\n" , 0 ;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 12416 KB Output is correct
2 Correct 27 ms 12544 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 12672 KB Output is correct
2 Correct 36 ms 12928 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 18924 KB Output is correct
2 Correct 254 ms 18236 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 22844 KB Output is correct
2 Correct 455 ms 23956 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 26744 KB Output is correct
2 Correct 728 ms 30072 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 15096 KB Output is correct
2 Correct 99 ms 14712 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 17400 KB Output is correct
2 Correct 292 ms 16632 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 18808 KB Output is correct
2 Correct 399 ms 19264 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 20704 KB Output is correct
2 Correct 678 ms 21112 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 895 ms 25976 KB Output is correct
2 Correct 764 ms 24848 KB Output is correct