Submission #200095

#TimeUsernameProblemLanguageResultExecution timeMemory
200095SaboonTransport (COCI19_transport)C++14
130 / 130
544 ms17764 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; const int maxn = 1e5 + 10; ll a[maxn]; vector<pair<int,int> > t[maxn]; bool mark[maxn]; vector<ll> DP, PD; int sz[maxn], cent; ll dp[maxn], pd[maxn], s[maxn]; ll answer = 0; void dfs_add(int v, int par){ PD.push_back(pd[v]); if (dp[v] >= 0) DP.push_back(s[v]); for (auto edge : t[v]){ int u = edge.first; if (u == par or mark[u]) continue; dfs_add(u, v); } } void dfs(int v, int par = -1){ if (par != -1){ if (dp[v] >= 0){ ll me = s[v]; int idx = upper_bound(PD.begin(), PD.end(), me) - PD.begin(); answer += idx; } int siz = DP.size(); int idx = lower_bound(DP.begin(), DP.end(), pd[v]) - DP.begin(); answer += siz - idx; } for (auto edge : t[v]){ int u = edge.first, w = edge.second; if (u == par or mark[u]) continue; s[u] = s[v] - w + a[u]; dp[u] = min(dp[v] - w + a[u], a[u] - w); pd[u] = max(pd[v], w - (a[cent] + s[v])); dfs(u, v); if (par == -1){ dfs_add(u, v); sort(DP.begin(), DP.end()); sort(PD.begin(), PD.end()); } } } int dfs_sz(int v, int par = -1){ sz[v] = 1; for (auto edge : t[v]){ int u = edge.first; if (u != par and !mark[u]) sz[v] += dfs_sz(u, v); } return sz[v]; } void centroid_decom(int v){ int Max = dfs_sz(v), par = -1; bool found = 1; while (found){ found = 0; for (auto edge : t[v]){ int u = edge.first; if (mark[u] or u == par) continue; if (sz[u] >= Max / 2){ par = v; v = u; found = 1; break; } } } cent = v; DP.clear(); PD.clear(); dp[v] = 0, pd[v] = 0; s[v] = 0; DP.push_back(s[v]); PD.push_back(pd[v]); dfs(v); mark[v] = 1; for (auto edge : t[v]){ int u = edge.first; if (!mark[u]) centroid_decom(u); } } int main(){ ios_base::sync_with_stdio(false); int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 0; i < n - 1; i++){ int v, u, w; cin >> v >> u >> w; t[v].push_back({u, w}); t[u].push_back({v, w}); } centroid_decom(1); cout << answer << 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...