oj.uz

Submission #873357

# Submission time Handle Problem Language Result Execution time Memory
873357 2023-11-14T23:06:49 Z sleepntsheep Paths (RMI21_paths) C++17
19 / 100
 600 ms 32084 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][N], 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);

    if (n <= 2000)
    {
        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 41 ms 31960 KB Output is correct
2 Correct 41 ms 31836 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 31960 KB Output is correct
2 Correct 41 ms 31836 KB Output is correct
3 Correct 434 ms 32084 KB Output is correct
4 Correct 437 ms 31832 KB Output is correct
5 Correct 428 ms 31972 KB Output is correct
6 Correct 429 ms 31976 KB Output is correct
7 Correct 428 ms 31972 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 31960 KB Output is correct
2 Correct 41 ms 31836 KB Output is correct
3 Correct 434 ms 32084 KB Output is correct
4 Correct 437 ms 31832 KB Output is correct
5 Correct 428 ms 31972 KB Output is correct
6 Correct 429 ms 31976 KB Output is correct
7 Correct 428 ms 31972 KB Output is correct
8 Execution timed out 1006 ms 32000 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 31960 KB Output is correct
2 Correct 41 ms 31836 KB Output is correct
3 Correct 434 ms 32084 KB Output is correct
4 Correct 437 ms 31832 KB Output is correct
5 Correct 428 ms 31972 KB Output is correct
6 Correct 429 ms 31976 KB Output is correct
7 Correct 428 ms 31972 KB Output is correct
8 Execution timed out 1006 ms 32000 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 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 41 ms 31960 KB Output is correct
2 Correct 41 ms 31836 KB Output is correct
3 Correct 434 ms 32084 KB Output is correct
4 Correct 437 ms 31832 KB Output is correct
5 Correct 428 ms 31972 KB Output is correct
6 Correct 429 ms 31976 KB Output is correct
7 Correct 428 ms 31972 KB Output is correct
8 Execution timed out 1006 ms 32000 KB Time limit exceeded
9 Halted 0 ms 0 KB -