oj.uz

Submission #361242

# Submission time Handle Problem Language Result Execution time Memory
361242 2021-01-28T21:35:27 Z jainbot27 Transport (COCI19_transport) C++17
130 / 130
 928 ms 31724 KB 
//copied cause im not spending any more time doing stupid constant optimization 
#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 24 ms 12396 KB Output is correct
2 Correct 27 ms 12524 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 12800 KB Output is correct
2 Correct 33 ms 12908 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 19456 KB Output is correct
2 Correct 257 ms 18668 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 22124 KB Output is correct
2 Correct 485 ms 23276 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 27884 KB Output is correct
2 Correct 738 ms 31724 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 15076 KB Output is correct
2 Correct 109 ms 14828 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 17516 KB Output is correct
2 Correct 325 ms 16824 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 18796 KB Output is correct
2 Correct 457 ms 19180 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 20716 KB Output is correct
2 Correct 674 ms 21228 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 928 ms 23540 KB Output is correct
2 Correct 810 ms 24940 KB Output is correct