oj.uz

Submission #848674

# Submission time Handle Problem Language Result Execution time Memory
848674 2023-09-13T08:40:24 Z TahirAliyev Paths (RMI21_paths) C++17
56 / 100
 190 ms 848 KB 
#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

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);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 39 ms 344 KB Output is correct
9 Correct 32 ms 620 KB Output is correct
10 Correct 22 ms 344 KB Output is correct
11 Correct 35 ms 344 KB Output is correct
12 Correct 26 ms 344 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 39 ms 344 KB Output is correct
9 Correct 32 ms 620 KB Output is correct
10 Correct 22 ms 344 KB Output is correct
11 Correct 35 ms 344 KB Output is correct
12 Correct 26 ms 344 KB Output is correct
13 Correct 190 ms 848 KB Output is correct
14 Correct 171 ms 716 KB Output is correct
15 Correct 98 ms 600 KB Output is correct
16 Correct 183 ms 640 KB Output is correct
17 Correct 132 ms 600 KB Output is correct
18 Correct 102 ms 804 KB Output is correct
19 Correct 187 ms 636 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 39 ms 344 KB Output is correct
9 Correct 32 ms 620 KB Output is correct
10 Correct 22 ms 344 KB Output is correct
11 Correct 35 ms 344 KB Output is correct
12 Correct 26 ms 344 KB Output is correct
13 Correct 190 ms 848 KB Output is correct
14 Correct 171 ms 716 KB Output is correct
15 Correct 98 ms 600 KB Output is correct
16 Correct 183 ms 640 KB Output is correct
17 Correct 132 ms 600 KB Output is correct
18 Correct 102 ms 804 KB Output is correct
19 Correct 187 ms 636 KB Output is correct
20 Runtime error 1 ms 600 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -