oj.uz

Submission #873356

# Submission time Handle Problem Language Result Execution time Memory
873356 2023-11-14T23:06:00 Z sleepntsheep Paths (RMI21_paths) C++17
36 / 100
 600 ms 2424 KB 
#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll = long long;
using ld = long double;
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false)

#define N 2005
#define ALL(x) x.begin(), x.end()

int n, k;
vector<pair<int, int>> g[N];

ll dp[N][103], sz[N];

void dfs1(int u, int p)
{
    dp[u][0] = 0;
    sz[u] = 1;
    dp[u][1] = 0;
    if (g[u].size() == 1 && u != p)
    {
        sz[u] = 1;
        dp[u][1] = 0;
    }
    for (auto [w, v] : g[u]) if (v != p)
    {
        dfs1(v, u);
        for (int i = sz[u]; i >= 0; --i)
            for (int j = 1; i+j <= k && j <= sz[v]; ++j)
                dp[u][i+j] = max(dp[u][i+j], dp[u][i] + dp[v][j] + w);
        sz[u] += sz[v];
    }
}

ll oneroot(int u)
{
    memset(dp, 0xbf, sizeof dp);
    memset(sz, 0, sizeof sz);
    dfs1(u, u);
    return dp[u][k];
}

int main()
{
    ShinLena;
    cin >> n >> k;
    for (int u, v, w, i = 1; i < n; ++i) cin >> u >> v >> w, g[u].emplace_back(w, v), g[v].emplace_back(w, u);

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

    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2140 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 9 ms 2152 KB Output is correct
4 Correct 9 ms 2152 KB Output is correct
5 Correct 9 ms 2136 KB Output is correct
6 Correct 8 ms 2140 KB Output is correct
7 Correct 8 ms 2152 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2140 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 9 ms 2152 KB Output is correct
4 Correct 9 ms 2152 KB Output is correct
5 Correct 9 ms 2136 KB Output is correct
6 Correct 8 ms 2140 KB Output is correct
7 Correct 8 ms 2152 KB Output is correct
8 Correct 176 ms 2140 KB Output is correct
9 Correct 173 ms 2236 KB Output is correct
10 Correct 113 ms 2140 KB Output is correct
11 Correct 358 ms 2140 KB Output is correct
12 Correct 158 ms 2424 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2140 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 9 ms 2152 KB Output is correct
4 Correct 9 ms 2152 KB Output is correct
5 Correct 9 ms 2136 KB Output is correct
6 Correct 8 ms 2140 KB Output is correct
7 Correct 8 ms 2152 KB Output is correct
8 Correct 176 ms 2140 KB Output is correct
9 Correct 173 ms 2236 KB Output is correct
10 Correct 113 ms 2140 KB Output is correct
11 Correct 358 ms 2140 KB Output is correct
12 Correct 158 ms 2424 KB Output is correct
13 Execution timed out 1070 ms 2228 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2140 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 9 ms 2152 KB Output is correct
4 Correct 9 ms 2152 KB Output is correct
5 Correct 9 ms 2136 KB Output is correct
6 Correct 8 ms 2140 KB Output is correct
7 Correct 8 ms 2152 KB Output is correct
8 Correct 176 ms 2140 KB Output is correct
9 Correct 173 ms 2236 KB Output is correct
10 Correct 113 ms 2140 KB Output is correct
11 Correct 358 ms 2140 KB Output is correct
12 Correct 158 ms 2424 KB Output is correct
13 Execution timed out 1070 ms 2228 KB Time limit exceeded
14 Halted 0 ms 0 KB -