Submission #497968

#TimeUsernameProblemLanguageResultExecution timeMemory
497968abc864197532Janjetina (COCI21_janjetina)C++17
110 / 110
441 ms22224 KiB
#include <bits/stdc++.h> using namespace std; #define lli long long int #define mp make_pair #define pb push_back #define eb emplace_back #define pii pair <int, int> #define X first #define Y second #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() void abc() {cout << endl;} template <typename T, typename ...U> void abc(T a, U ...b) { cout << a << ' ', abc(b...); } template <typename T> void printv(T l, T r) { while (l != r) cout << *l << " \n"[++l == r]; } template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) { return o >> a.X >> a.Y; } template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) { return o << '(' << a.X << ", " << a.Y << ')'; } template <typename T> ostream& operator << (ostream& o, vector<T> a) { if (a.empty()) return o << "{}"; bool is = false; for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;} return o << '}'; } template <typename T> struct vv : vector <vector <T>> { vv(int n, int m, T v) : vector <vector <T>> (n, vector <T>(m, v)) {} vv() {} }; template <typename T> struct vvv : vector <vv <T>> { vvv(int n, int m, int k, T v) : vector <vv <T>> (n, vv <T>(m, k, v)) {} vvv() {} }; #ifdef Doludu #define test(args...) abc("[" + string(#args) + "]", args) #define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout) #else #define test(args...) void(0) #define owo ios::sync_with_stdio(false); cin.tie(0) #endif const int mod = 1e9 + 7, N = 100010, logN = 17, K = 350, M = N * 40; int k; vector <pii> adj[N]; int sz[N]; bool vis[N]; void dfssz(int v, int pa) { sz[v] = 1; for (auto [u, w] : adj[v]) if (u != pa && !vis[u]) { dfssz(u, v); sz[v] += sz[u]; } } int dfscen(int v, int pa, int n) { for (auto [u, w] : adj[v]) if (u != pa && !vis[u] && sz[u] * 2 > n) return dfscen(u, v, n); return v; } struct BIT { int val[N]; vector <int> move; BIT () { fill(val, val + N, 0); } void add(int p, int v) { p += 3; for (int i = p; i < N; i += i & (-i)) val[i] += v, move.pb(i); } int query(int p) { p += 3; int ans = 0; for (int i = p; i > 0; i -= i & (-i)) ans += val[i]; return ans; } void reset() { for (int i : move) val[i] = 0; move.clear(); } } bit; lli ans; // max(mx[a], mx[b]) - dp[a] >= k + dp[b] // mx[a] > mx[b] -> mx[a] - dp[a] >= k + dp[b] // k + dep[b] <= mx[a] - dep[a] vector <int> all, cc; int mx[N], dep[N]; lli calc() { sort(all(cc), [&](int i, int j) { return mx[i] < mx[j]; }); lli cur = 0; for (int i : cc) { cur += bit.query(mx[i] - dep[i]); bit.add(k + dep[i], 1); } bit.reset(); return cur; } void dfsans(int v, int pa) { if (~pa) cc.pb(v); else mx[v] = dep[v] = 0; for (auto [u, w] : adj[v]) if (u != pa && !vis[u]) { mx[u] = max(mx[v], w); dep[u] = dep[v] + 1; if (mx[u] - dep[u] >= k) ans++; dfsans(u, v); if (pa == -1) { ans -= calc(); for (int i : cc) all.pb(i); cc.clear(); } } if (pa == -1) { swap(all, cc); ans += calc(); cc.clear(); } } void dfscd(int v, int pa) { dfssz(v, pa); int c = dfscen(v, pa, sz[v]); vis[c] = true; dfsans(c, -1); for (auto [u, w] : adj[c]) if (!vis[u]) dfscd(u, c); } int main () { owo; int n; cin >> n >> k; for (int i = 0, u, v, w; i < n - 1; ++i) { cin >> u >> v >> w, --u, --v; adj[u].eb(v, w), adj[v].eb(u, w); } dfscd(0, -1); cout << ans * 2 << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...