oj.uz

답안 #687675

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
687675 2023-01-26T19:40:33 Z QwertyPi Paths (RMI21_paths) C++14
8 / 100
 600 ms 13232 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 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]){

    }
}
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);
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2660 KB Output is correct

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2660 KB Output is correct
3 Correct 4 ms 2644 KB Output is correct
4 Correct 4 ms 2644 KB Output is correct
5 Correct 4 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Incorrect 3 ms 2644 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2660 KB Output is correct
3 Correct 4 ms 2644 KB Output is correct
4 Correct 4 ms 2644 KB Output is correct
5 Correct 4 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Incorrect 3 ms 2644 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2660 KB Output is correct
3 Correct 4 ms 2644 KB Output is correct
4 Correct 4 ms 2644 KB Output is correct
5 Correct 4 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Incorrect 3 ms 2644 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1081 ms 13232 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2660 KB Output is correct
3 Correct 4 ms 2644 KB Output is correct
4 Correct 4 ms 2644 KB Output is correct
5 Correct 4 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Incorrect 3 ms 2644 KB Output isn't correct
8 Halted 0 ms 0 KB -