Submission #929056

#TimeUsernameProblemLanguageResultExecution timeMemory
929056Amirreza_FakhriJanjetina (COCI21_janjetina)C++17
110 / 110
303 ms17952 KiB
// In the name of the God #include <bits/stdc++.h> #define ll long long #define int long long #define pb push_back #define F first #define S second #define mp make_pair #define pii pair <int, int> #define smin(x, y) (x) = min((x), (y)) #define smax(x, y) (x) = max((x), (y)) #define all(x) (x).begin(), (x).end() using namespace std; const int inf = 1e9+7; const int mod = 998244353; const int maxn = 1e5+5; int n, k, sz[maxn], fen[maxn]; bool mark[maxn]; vector <pii> adj[maxn], vec1, vec2; void dfs1(int v, int p) { sz[v] = 1; for (pii e : adj[v]) { int u = e.F; if (!mark[u] and u != p) { dfs1(u, v); sz[v] += sz[u]; } } } int fcen(int v, int p, int s) { for (pii e : adj[v]) { int u = e.F; if (!mark[u] and u != p and sz[u]*2 > s) return fcen(u, v, s); } return v; } void dfs2(int v, int p, int mx, int h) { vec1.pb(mp(mx, h)), vec2.pb(mp(mx, h)); for (pii e : adj[v]) { int u = e.F; if (!mark[u] and u != p) dfs2(u, v, max(mx, e.S), h+1); } } void upd(int i, int x) { i++; for (; i <= n; i += i&(-i)) fen[i] += x; } int get(int i) { i++; int ans = 0; for (; i; i -= i&(-i)) ans += fen[i] ; return ans; } int relax(vector <pii> &vec) { int res = 0; sort(all(vec)); for (pii p : vec) { int j = p.F-k-p.S; if (j >= 0) res += get(min(j, n-1)); upd(p.S, 1); } for (pii p : vec) upd(p.S, -1); vec.clear(); return res; } int cen(int v) { dfs1(v, v); v = fcen(v, v, sz[v]); int ans = 0; vec2.pb(mp(0, 0)); for (pii e : adj[v]) { int u = e.F; if (!mark[u]) { dfs2(u, v, e.S, 1); ans -= relax(vec1); } } ans += relax(vec2); mark[v] = 1; for (pii e : adj[v]) { int u = e.F; if (!mark[u]) ans += cen(u); } return ans; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; for (int i = 1; i < n; i++) { int v, u, w; cin >> v >> u >> w; adj[--v].pb(mp(--u, w)); adj[u].pb(mp(v, w)); } cout << cen(0)*2 << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...