Submission #848429

#TimeUsernameProblemLanguageResultExecution timeMemory
848429TahirAliyevPaths (RMI21_paths)C++17
36 / 100
654 ms1036 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], rtimeIn[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[2 * node] += lazy[node]; lazy[2 * node + 1] += lazy[node]; } lazy[node] = 0; } void build(int node, int l, int r){ if(l == r){ segTree[node] = {pathVal[rtimeIn[l]], rtimeIn[l]}; return; } int mid = (l + r) / 2; build(2 * node, l, mid); build(2 * node + 1, mid + 1, r); segTree[node] = max(segTree[2 * node], segTree[2 * node + 1]); } void update(int node, int l, int r, int ul, int ur, ll 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) / 2; update(2 * node, l, mid, ul, ur, val); update(2 * node + 1, mid + 1, r, ul, ur, val); segTree[node] = max(segTree[2 * node], segTree[2 * node + 1]); } int t = 0; void dfs(int node, int p, ll h){ timeIn[node] = ++t; rtimeIn[t] = node; pathVal[node] = h; for(pii to : g[node]){ if(p == to.first) continue; par[to.first] = make_pair(node, to.second); dfs(to.first, node, h + to.second); } 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(lazy, 0, sizeof(lazy)); memset(marked, 0, sizeof(marked)); dfs(i, i, 0); build(1, 1, n); 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){ if(marked[a]) break; update(1, 1, n, 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:71:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     scanf("%d%d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:73:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         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...