oj.uz

Submission #246727

# Submission time Handle Problem Language Result Execution time Memory
246727 2020-07-10T03:27:40 Z MohamedAhmed04 Transport (COCI19_transport) C++14
0 / 130
 658 ms 65540 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({x * -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) ;
	}
}

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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 13688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 15096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 322 ms 53376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 404 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 416 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 31072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 199 ms 29280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 442 ms 47480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 652 ms 59444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 658 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -