Submission #645762

#TimeUsernameProblemLanguageResultExecution timeMemory
645762notmePaths (RMI21_paths)C++14
19 / 100
1083 ms6344 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; const long long MAXN = 1005; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } long long n, k; map < pair < long long, long long >, long long > mp; long long c[MAXN]; vector < long long > g[MAXN]; vector < long long > v[MAXN]; void read() { cin >> n >> k; long long xx, yy, cc; for (long long i = 1; i < n; ++ i) { cin >> xx >> yy >> cc; mp[make_pair(xx, yy)] = i; mp[make_pair(yy, xx)] = i; g[xx].push_back(yy); g[yy].push_back(xx); c[i] = cc; } } long long p[MAXN], used[MAXN]; void dfs(long long beg) { used[beg] = 1; long long nb; for (long long i = 0; i < g[beg].size(); ++ i) { nb = g[beg][i]; if(!used[nb]) { dfs(nb); p[nb] = beg; } } } long long sum[MAXN]; long long r; void jump(long long vertex) { long long leaf = vertex; while(vertex != r) { long long nomer = mp[make_pair(vertex, p[vertex])]; v[nomer].push_back(leaf); sum[leaf] += c[nomer]; vertex = p[vertex]; } } long long c1[MAXN]; void make_zero(long long vertex) { long long leaf = vertex; while(vertex != r) { //if(vertex)cout << vertex << endl; long long nomer = mp[make_pair(vertex, p[vertex])]; for (long long j = 0; j < v[nomer].size(); ++ j) { sum[v[nomer][j]] -= c1[nomer]; // c[nomer] = 0; } c1[nomer] = 0; vertex = p[vertex]; } } void solve_for_root(long long root) { memset(sum, 0, sizeof(sum)); memset(used, 0, sizeof(used)); memset(p, 0, sizeof(p)); r = root; dfs(root); for (long long i = 1; i < n; ++ i) c1[i] = c[i]; for (long long i = 1; i <= n; ++ i) { // cout << p[i] << " "; v[i].clear(); } //cout << endl; for (long long i = 1; i <= n; ++ i) { jump(i); // cout << sum[i] << " "; } // cout << endl; // cout << "nere???" << endl; long long ans = 0; for (long long i = 1; i <= k; ++ i) { long long maxsum = 0, maxidx = 0; for (long long j = 1; j <= n; ++ j) { if(sum[j] > maxsum) { maxsum = sum[j]; maxidx = j; } } //cout << "ended" << " " << maxidx << endl; ans += maxsum; make_zero(maxidx); /* for (long long j = 1; j <= n; ++ j) cout << sum[j] << " "; cout << endl;*/ } cout << ans << endl; } int main() { speed(); read(); for (long long i = 1; i <= n; ++ i) solve_for_root(i); return 0; }

Compilation message (stderr)

Main.cpp: In function 'void dfs(long long int)':
Main.cpp:35:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (long long i = 0; i < g[beg].size(); ++ i)
      |                           ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'void make_zero(long long int)':
Main.cpp:66:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (long long j = 0; j < v[nomer].size(); ++ j)
      |                               ~~^~~~~~~~~~~~~~~~~
Main.cpp:61:15: warning: unused variable 'leaf' [-Wunused-variable]
   61 |     long long leaf = vertex;
      |               ^~~~
#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...