Submission #733741

#TimeUsernameProblemLanguageResultExecution timeMemory
733741GrindMachineTransport (COCI19_transport)C++17
130 / 130
275 ms26580 KiB
// Om Namah Shivaya #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x, y) ((x + y - 1) / (y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i, n) for(int i = 0; i < n; ++i) #define rep1(i, n) for(int i = 1; i <= n; ++i) #define rev(i, s, e) for(int i = s; i >= e; --i) #define trav(i, a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a, b); } template<typename T> void amax(T &a, T b) { a = max(a, b); } #ifdef LOCAL #include "debug.h" #else #define debug(x) 42 #endif /* */ const int MOD = 1e9 + 7; const int N = 1e5 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; vector<pll> adj[N]; vector<ll> a(N); vector<bool> rem(N); vector<ll> subsiz(N); ll dfs1(ll u, ll p) { subsiz[u] = 1; for (auto [v, w] : adj[u]) { if (v == p or rem[v]) conts; subsiz[u] += dfs1(v, u); } return subsiz[u]; } ll dfs2(ll u, ll p, ll nodes) { for (auto [v, w] : adj[u]) { if (v == p or rem[v]) conts; if (subsiz[v] > nodes / 2) { return dfs2(v, u, nodes); } } return u; } vector<ll> sumup(N), mnprefup(N); vector<array<ll, 3>> here[N]; ll curr_centroid; vector<ll> sub_roots; void dfs3(ll u, ll p, ll uu, ll sumdown, ll mnprefdown) { here[curr_centroid].pb({sumup[u], mnprefup[u], mnprefdown}); if (uu != -1) { here[uu].pb({sumup[u], mnprefup[u], mnprefdown}); } for (auto [v, w] : adj[u]) { if (v == p or rem[v]) conts; sumup[v] = a[v] - w + sumup[u]; mnprefup[v] = min(a[v] - w, a[v] - w + mnprefup[u]); ll uu2 = uu; if (uu == -1) { uu2 = v; sub_roots.pb(v); } dfs3(v, u, uu2, sumdown + a[u] - w, min(mnprefdown, sumdown + a[u] - w)); } } ll get(vector<array<ll, 3>> v) { vector<ll> vals; for (auto [sum, mnprefup, mnprefdown] : v) { vals.pb(mnprefdown); } sort(all(vals)); ll res = 0; for (auto [sum, mnprefup, mnprefdown] : v) { if (mnprefup < 0) conts; ll cnt = vals.end() - lower_bound(all(vals), -sum); if (mnprefdown >= -sum) { cnt--; } res += cnt; } return res; } ll ans = 0; void build(ll u, ll p) { ll nodes = dfs1(u, -1); ll centroid = dfs2(u, -1, nodes); rem[centroid] = 1; sumup[centroid] = 0; mnprefup[centroid] = 0; curr_centroid = centroid; sub_roots.clear(); dfs3(centroid, -1, -1, 0, 0); trav(v, sub_roots) { ans -= get(here[v]); here[v].clear(); here[v].shrink_to_fit(); } ans += get(here[centroid]); here[centroid].clear(); here[centroid].shrink_to_fit(); for (auto [v, w] : adj[centroid]) { if (rem[v]) conts; build(v, centroid); } } void solve(int test_case) { ll n; cin >> n; rep1(i, n) cin >> a[i]; rep1(i, n - 1) { ll u, v, w; cin >> u >> v >> w; adj[u].pb({v, w}), adj[v].pb({u, w}); } build(1, -1); cout << ans << endl; } int main() { fastio; int t = 1; // cin >> t; rep1(i, t) { solve(i); } return 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...