oj.uz

Submission #687677

# Submission time Handle Problem Language Result Execution time Memory
687677 2023-01-26T19:53:36 Z QwertyPi Paths (RMI21_paths) C++14
56 / 100
 600 ms 12472 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 1e5 + 11;
vector<pair<int, int>> G[MAXN];
int w[MAXN], mx_dis[MAXN];
int to[MAXN], a[MAXN], l[MAXN], r[MAXN];
int leaf_cnt = 0;
void dfs(int v, int pa = -1){
    int sons_cnt = 0;
    l[v] = MAXN, r[v] = -1;
    for(auto& [u, we] : G[v]){
        if(u != pa){
            sons_cnt++;
            w[u] = we; dfs(u, v);
            if(mx_dis[u] + w[u] > mx_dis[v]){
                to[v] = to[u];
                mx_dis[v] = mx_dis[u] + w[u];
            }
            l[v] = min(l[v], l[u]), r[v] = max(r[v], r[u]);
        }
    }
    if(sons_cnt == 0){
        to[v] = ++leaf_cnt; l[v] = r[v] = leaf_cnt;
    }
    a[to[v]] += w[v];
}

void dfs2(int v, int pa = -1){
    for(auto& [u, we] : G[v]){

    }
}
int32_t main(){
    int N, K; cin >> N >> K;
    for(int i = 0; i < N - 1; i++){
        int u, v, w; cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }

    for(int i = 1; i <= N; i++){
        fill(a + 1, a + N + 1, 0);
        fill(mx_dis + 1, mx_dis + N + 1, 0);
        fill(w + 1, w + N + 1, 0);
        fill(to + 1, to + N + 1, 0);
        fill(l + 1, l + N + 1, 0);
        fill(r + 1, r + N + 1, 0);
        leaf_cnt = 0;
        dfs(i);
        sort(a + 1, a + leaf_cnt + 1, [](int x, int y){ return x > y; });
        int ans = 0;
        for(int i = 1; i <= K; i++) ans += a[i];
        cout << ans << endl;
    }
}

Compilation message

Main.cpp: In function 'void dfs(long long int, long long int)':
Main.cpp:13:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   13 |     for(auto& [u, we] : G[v]){
      |               ^
Main.cpp: In function 'void dfs2(long long int, long long int)':
Main.cpp:31:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     for(auto& [u, we] : G[v]){
      |               ^
Main.cpp:31:15: warning: unused structured binding declaration [-Wunused-variable]
   31 |     for(auto& [u, we] : G[v]){
      |               ^~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 4 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 45 ms 2792 KB Output is correct
9 Correct 41 ms 2868 KB Output is correct
10 Correct 32 ms 2820 KB Output is correct
11 Correct 52 ms 2804 KB Output is correct
12 Correct 33 ms 2804 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 4 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 45 ms 2792 KB Output is correct
9 Correct 41 ms 2868 KB Output is correct
10 Correct 32 ms 2820 KB Output is correct
11 Correct 52 ms 2804 KB Output is correct
12 Correct 33 ms 2804 KB Output is correct
13 Correct 185 ms 2920 KB Output is correct
14 Correct 184 ms 3020 KB Output is correct
15 Correct 129 ms 3024 KB Output is correct
16 Correct 192 ms 2904 KB Output is correct
17 Correct 144 ms 3056 KB Output is correct
18 Correct 102 ms 2876 KB Output is correct
19 Correct 184 ms 3032 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 12472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 4 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 45 ms 2792 KB Output is correct
9 Correct 41 ms 2868 KB Output is correct
10 Correct 32 ms 2820 KB Output is correct
11 Correct 52 ms 2804 KB Output is correct
12 Correct 33 ms 2804 KB Output is correct
13 Correct 185 ms 2920 KB Output is correct
14 Correct 184 ms 3020 KB Output is correct
15 Correct 129 ms 3024 KB Output is correct
16 Correct 192 ms 2904 KB Output is correct
17 Correct 144 ms 3056 KB Output is correct
18 Correct 102 ms 2876 KB Output is correct
19 Correct 184 ms 3032 KB Output is correct
20 Execution timed out 1078 ms 12472 KB Time limit exceeded
21 Halted 0 ms 0 KB -