Submission #361242

#TimeUsernameProblemLanguageResultExecution timeMemory
361242jainbot27Transport (COCI19_transport)C++17
130 / 130
928 ms31724 KiB
//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 ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...