oj.uz

Submission #509719

# Submission time Handle Problem Language Result Execution time Memory
509719 2022-01-14T08:37:43 Z Rainbowbunny Paths (RMI21_paths) C++17
56 / 100
 600 ms 10180 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXN = 1e5 + 5;

int n, k;
ll mx[MAXN];
pair <ll, int> dp[MAXN];
vector <pair <int, ll> > Adj[MAXN];

void DFS(int node, int p = -1)
{
    for(auto x : Adj[node])
    {
        if(x.first == p)
        {
            continue;
        }
        DFS(x.first, node);
        dp[x.first].first += x.second;
        dp[node] = max(dp[node], dp[x.first]);
    }
    if(dp[node].second == 0)
    {
        dp[node] = make_pair(0, node);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    if(n > MAXN)
    {
        return 0;
    }
    for(int i = 1; i < n; i++)
    {
        int u, v, c;
        cin >> u >> v >> c;
        Adj[u].emplace_back(v, c);
        Adj[v].emplace_back(u, c);
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            mx[j] = 0;
            dp[j] = make_pair(0, 0);
        }
        DFS(i);
        for(int j = 1; j <= n; j++)
        {
            mx[dp[j].second] = max(mx[dp[j].second], dp[j].first);
        }
        sort(mx + 1, mx + n + 1, greater <ll> ());
        ll ans = 0;
        for(int j = 1; j <= k; j++)
        {
            ans += mx[j];
        }
        cout << ans << '\n';
    }
}

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2604 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 48 ms 2756 KB Output is correct
9 Correct 47 ms 2820 KB Output is correct
10 Correct 46 ms 2796 KB Output is correct
11 Correct 45 ms 2748 KB Output is correct
12 Correct 34 ms 2756 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2604 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 48 ms 2756 KB Output is correct
9 Correct 47 ms 2820 KB Output is correct
10 Correct 46 ms 2796 KB Output is correct
11 Correct 45 ms 2748 KB Output is correct
12 Correct 34 ms 2756 KB Output is correct
13 Correct 215 ms 2840 KB Output is correct
14 Correct 299 ms 3056 KB Output is correct
15 Correct 131 ms 2892 KB Output is correct
16 Correct 196 ms 2832 KB Output is correct
17 Correct 154 ms 2836 KB Output is correct
18 Correct 112 ms 2824 KB Output is correct
19 Correct 228 ms 2824 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1018 ms 10180 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 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2604 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 48 ms 2756 KB Output is correct
9 Correct 47 ms 2820 KB Output is correct
10 Correct 46 ms 2796 KB Output is correct
11 Correct 45 ms 2748 KB Output is correct
12 Correct 34 ms 2756 KB Output is correct
13 Correct 215 ms 2840 KB Output is correct
14 Correct 299 ms 3056 KB Output is correct
15 Correct 131 ms 2892 KB Output is correct
16 Correct 196 ms 2832 KB Output is correct
17 Correct 154 ms 2836 KB Output is correct
18 Correct 112 ms 2824 KB Output is correct
19 Correct 228 ms 2824 KB Output is correct
20 Execution timed out 1018 ms 10180 KB Time limit exceeded
21 Halted 0 ms 0 KB -