Submission #642091

#TimeUsernameProblemLanguageResultExecution timeMemory
642091vovamrTransport (COCI19_transport)C++17
0 / 130
774 ms15676 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define fi first #define se second #define ll long long #define ld long double #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define pb push_back #define mpp make_pair #define ve vector using namespace std; using namespace __gnu_pbds; template<class T> using oset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>; const ll inf = 1e18; const int iinf = 1e9; typedef pair<ll, ll> pll; typedef pair<int, int> pii; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); } template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); } const int N = 1e5 + 10; ve<pii> gr[N]; int sz[N], used[N], a[N]; inline void dfs1(int v, int p) { sz[v] = 1; for (auto &[to, w] : gr[v]) { if (used[to] || to == p) continue; dfs1(to, v); sz[v] += sz[to]; } } inline int centroid(int v, int p, int n) { for (auto &[to, w] : gr[v]) { if (used[to] || to == p || sz[to] <= n / 2) continue; return centroid(to, v, n); } return v; } ll ans = 0; int PTR = 0; pll al[N]; inline void dfs(int v, int p, ll cur_sum, ll mn_sum) { if (mn_sum >= 0) ++ans; al[PTR++] = {cur_sum, mn_sum}; for (auto &[to, w] : gr[v]) { if (to == p || used[to]) continue; ll s = cur_sum + a[v] - w; dfs(to, v, s, min(mn_sum, s)); } } oset<ll> sums; inline void dfs2(int v, int p, int pw, ll tot, ll mn_sum) { ll mn = min(0ll, a[v] - pw + mn_sum); if (mn >= 0) ans += 1 + sz(sums) - sums.order_of_key(-tot); for (auto &[to, w] : gr[v]) { if (to == p || used[to]) continue; dfs2(to, v, w, tot + a[v] - w, mn); } } inline void cd(int v, int p) { used[v] = 1; dfs1(v, p); PTR = 0; for (auto &[to, w] : gr[v]) { if (to == p || used[to]) continue; dfs(to, v, a[v] - w, a[v] - w); } sums.clear(); for (int i = 0; i < PTR; ++i) { auto &[sum, mn_sum] = al[i]; sums.insert(mn_sum); } int pos = 0; for (auto &[to, w] : gr[v]) { if (to == p || used[to]) continue; for (int i = pos; i < pos + sz[to]; ++i) { auto &[sum, mn_sum] = al[i]; sums.erase(sums.lower_bound(mn_sum - 1)); } dfs2(to, v, w, a[to] - w, 0); for (int i = pos; i < pos + sz[to]; ++i) { auto &[sum, mn_sum] = al[i]; sums.insert(mn_sum); } pos += sz[to]; } for (auto &[to, w] : gr[v]) { if (to == p || used[to]) continue; int c = centroid(to, v, sz[to]); cd(c, v); } } inline void solve() { int n; cin >> n; for (int i = 0; i < n; ++i) cin >> a[i]; for (int i = 1; i < n; ++i) { int v, u, w; cin >> v >> u >> w, --v, --u; gr[v].pb({u, w}), gr[u].pb({v, w}); } dfs1(0, 0); int c = centroid(0, 0, n); cd(c, c); cout << ans; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int q = 1; // cin >> q; while (q--) solve(); cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl; }
#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...