Submission #848674

#TimeUsernameProblemLanguageResultExecution timeMemory
848674TahirAliyevPaths (RMI21_paths)C++17
56 / 100
190 ms848 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; vector<pii> g[MAX]; vector<ll> val; int heavy[MAX]; ll dfs(int node, int p){ pii m = {0, 0}; for(pii to : g[node]){ if(p == to.first) continue; ll a = dfs(to.first, node) + to.second; if(m.first < a){ m = {a, to.first}; } } heavy[node] = m.second; return m.first; } void dfs2(int node, int p, ll h){ if(g[node].size() == 1 && p != node){ val.push_back(h); return; } for(pii to : g[node]){ if(p == to.first) continue; if(heavy[node] == to.first){ dfs2(heavy[node], node, h + to.second); } else{ dfs2(to.first, node, to.second); } } } 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++){ val.clear(); memset(heavy, 0, sizeof(heavy)); dfs(i, i); dfs2(i, i, 0); sort(val.begin(), val.end()); ll ans = 0; for(int i = val.size() - 1; i >= max(int(val.size() - k), 0); i--){ ans += val[i]; } cout << ans << '\n'; } }

Compilation message (stderr)

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