oj.uz

답안 #858380

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
858380 2023-10-08T09:47:50 Z thangdz2k7 Paths (RMI21_paths) C++17
56 / 100
 600 ms 10064 KB 
#include <bits/stdc++.h>
#define ii pair <int, int>
#define F first
#define S second

using namespace std;

const int mod = 1e9 + 7;
const int N = 1e5 + 5;

int n, k, dem;
vector <ii> c[N];
long long ans[N];
long long dp[N];

void dfs(int u, int pa){
    dp[u] = 0;
    for (ii v : c[u]){
        if (v.F == pa) continue;
        dfs(v.F, u);
        dp[u] = max(dp[u], dp[v.F] + v.S);
    }

    bool used = false;
    for (ii v : c[u]){
        if (v.F == pa) continue;
        if (used or dp[v.F] + v.S < dp[u]){
            ++ dem;
            ans[dem] = dp[v.F] + v.S;
        }
        else used = true;

    }
}

long long solve_single_root(int r){
    dem = 0;
    dfs(r, 0);
    ++ dem;
    ans[dem] = dp[r];
    sort(ans + 1, ans + dem + 1);
    long long res = 0;
    for (int i = dem; i >= max(1, dem - k + 1); -- i) {
        res += ans[i];
        //if (r == 1) cout << ans[i] << ' ';
    }
    return res;
}

void solve(){
    cin >> n >> k;
    for (int i = 1; i <= n - 1; ++ i){
        int u, v, w;
        cin >> u >> v >> w;
        c[u].push_back(ii(v, w));
        c[v].push_back(ii(u, w));
    }

    for (int i = 1; i <= n; ++ i) cout << solve_single_root(i) << '\n';
}

int main(){
    //freopen("code.inp", "r", stdin);
    //freopen("code.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t --) solve();

    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Correct 1 ms 4188 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 2 ms 4208 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Correct 1 ms 4188 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 2 ms 4208 KB Output is correct
8 Correct 31 ms 4188 KB Output is correct
9 Correct 26 ms 4188 KB Output is correct
10 Correct 19 ms 4700 KB Output is correct
11 Correct 34 ms 4188 KB Output is correct
12 Correct 22 ms 4188 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Correct 1 ms 4188 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 2 ms 4208 KB Output is correct
8 Correct 31 ms 4188 KB Output is correct
9 Correct 26 ms 4188 KB Output is correct
10 Correct 19 ms 4700 KB Output is correct
11 Correct 34 ms 4188 KB Output is correct
12 Correct 22 ms 4188 KB Output is correct
13 Correct 163 ms 4324 KB Output is correct
14 Correct 137 ms 4184 KB Output is correct
15 Correct 66 ms 4188 KB Output is correct
16 Correct 155 ms 4316 KB Output is correct
17 Correct 89 ms 4312 KB Output is correct
18 Correct 84 ms 4308 KB Output is correct
19 Correct 157 ms 4316 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Correct 1 ms 4188 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 2 ms 4208 KB Output is correct
8 Correct 31 ms 4188 KB Output is correct
9 Correct 26 ms 4188 KB Output is correct
10 Correct 19 ms 4700 KB Output is correct
11 Correct 34 ms 4188 KB Output is correct
12 Correct 22 ms 4188 KB Output is correct
13 Correct 163 ms 4324 KB Output is correct
14 Correct 137 ms 4184 KB Output is correct
15 Correct 66 ms 4188 KB Output is correct
16 Correct 155 ms 4316 KB Output is correct
17 Correct 89 ms 4312 KB Output is correct
18 Correct 84 ms 4308 KB Output is correct
19 Correct 157 ms 4316 KB Output is correct
20 Execution timed out 1048 ms 10064 KB Time limit exceeded
21 Halted 0 ms 0 KB -