Submission #687674

#	Time	Username	Problem	Language	Result	Execution time	Memory
687674		QwertyPi	Paths (RMI21_paths)	C++14	0 / 100	1084 ms	11164 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 11;
vector<pair<int, int>> G[MAXN];
int w[MAXN], mx_dis[MAXN];
int leaf_id[MAXN], 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){
        leaf_id[v] = ++leaf_cnt; 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]){

    }
}
int 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);
        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 (stderr)

Main.cpp: In function 'void dfs(int, 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(int, 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: 0 / 8
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32