Submission #848497

#TimeUsernameProblemLanguageResultExecution timeMemory
848497TahirAliyevPaths (RMI21_paths)C++17
36 / 100
622 ms1004 KiB
#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define ll long long int #define oo 1e9 #define pii pair<ll, int> const int MAX = 2002; int n, k; pii segTree[4 * MAX]; ll lazy[4 * MAX]; vector<pii> g[MAX]; int timeIn[MAX], timeOut[MAX], leafs[MAX]; ll pathVal[MAX]; bool marked[MAX]; pii par[MAX]; void relax(int node, int l, int r){ if(lazy[node] == 0) return; segTree[node].first += lazy[node]; if(l != r){ lazy[node << 1] += lazy[node]; lazy[node << 1 | 1] += lazy[node]; } lazy[node] = 0; } void build(int node, int l, int r){ lazy[node] = 0; if(l == r){ segTree[node] = {pathVal[leafs[l]], leafs[l]}; return; } int mid = (l + r) >> 1; build(node << 1, l, mid); build(node << 1 | 1, mid + 1, r); segTree[node] = max(segTree[node << 1], segTree[node << 1| 1]); } void update(int node, int l, int r, int ul, int ur, int val){ relax(node, l, r); if(ul > r || l > ur) return; if(ul <= l && r <= ur){ lazy[node] += val; relax(node, l, r); return; } int mid = (l + r) >> 1; update(node << 1, l, mid, ul, ur, val); update(node << 1 | 1, mid + 1, r, ul, ur, val); segTree[node] = max(segTree[node << 1], segTree[node << 1 | 1]); } int t = 1; void dfs(int node, int p, ll h){ timeIn[node] = t; pathVal[node] = h; for(pii to : g[node]){ if(p == to.first) continue; par[to.first] = {node, to.second}; dfs(to.first, node, h + to.second); } timeOut[node] = t - 1; if(g[node].size() == 1 && node != p){ leafs[t] = node; timeOut[node] = t++; } } int main(){ scanf("%d%d", &n, &k); for(int i = 1; i < n; i++){ int u, v, a; scanf("%d%d%d", &u, &v, &a); g[u].push_back({v, a}); g[v].push_back({u, a}); } for(int i = 1; i <= n; i++){ t = 0; memset(marked, 0, sizeof(marked)); dfs(i, i, 0); build(1, 0, t - 1); ll ans = 0; for(int j = 0; j < k; j++){ pii m = segTree[1]; if(m.first == 0) break; ans += m.first; int a = m.second; while(a != i && !marked[a]){ update(1, 0, t - 1, timeIn[a], timeOut[a], -par[a].second); marked[a] = true; a = par[a].first; } } cout << ans << '\n'; } }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     scanf("%d%d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:78:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         int u, v, a; scanf("%d%d%d", &u, &v, &a);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...