oj.uz

Submission #873359

# Submission time Handle Problem Language Result Execution time Memory
873359 2023-11-14T23:18:09 Z sleepntsheep Paths (RMI21_paths) C++17
48 / 100
 399 ms 19284 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 200005
#define ALL(x) x.begin(), x.end()

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

ll dp[1001][101], dp2[N], dp3[N], dp4[N];

void dfs1(int u, int p)
{
    dp[u][0] = dp[u][1] = 0;
    sz[u] = 1;
    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];
}

void dfs2(int u, int p)
{
    dp2[u] = 0;
    for (auto [w, v] : g[u]) if (v != p)
    {
        dfs2(v, u);
        if (dp2[v] + w >= dp2[u]) dp3[u] = dp2[u], dp2[u] = dp2[v] + w;
        else if (dp2[v] + w >= dp3[u]) dp3[u] = dp2[v] + w;
    }
}

void dfs3(int u, int p)
{
    for (auto [w, v] : g[u]) if (v != p)
    {
        if (dp2[v] + w == dp2[u]) dp4[v] = max(dp4[u] + w, dp3[u] + w);
        else dp4[v] = max(dp4[u] + w, dp2[u] + w);
        dfs3(v, u);
    }
}

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 (k == 1)
    {
        dfs2(1, 1);
        dfs3(1, 1);
        for (int i = 1; i <= n; ++i) cout << max(dp2[i], dp4[i]) << '\n';
    }
    else if (n <= 1002)
    {
        for (int i = 1; i <= n; ++i) cout << oneroot(i) << '\n';
    }
    else if (n <= 2000)
    {
    }
    else
    {
    }

    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 8 ms 7160 KB Output is correct
4 Correct 10 ms 7004 KB Output is correct
5 Correct 9 ms 7156 KB Output is correct
6 Correct 8 ms 7004 KB Output is correct
7 Correct 8 ms 7152 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 8 ms 7160 KB Output is correct
4 Correct 10 ms 7004 KB Output is correct
5 Correct 9 ms 7156 KB Output is correct
6 Correct 8 ms 7004 KB Output is correct
7 Correct 8 ms 7152 KB Output is correct
8 Correct 173 ms 7176 KB Output is correct
9 Correct 179 ms 7260 KB Output is correct
10 Correct 108 ms 7184 KB Output is correct
11 Correct 399 ms 7172 KB Output is correct
12 Correct 155 ms 7260 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 8 ms 7160 KB Output is correct
4 Correct 10 ms 7004 KB Output is correct
5 Correct 9 ms 7156 KB Output is correct
6 Correct 8 ms 7004 KB Output is correct
7 Correct 8 ms 7152 KB Output is correct
8 Correct 173 ms 7176 KB Output is correct
9 Correct 179 ms 7260 KB Output is correct
10 Correct 108 ms 7184 KB Output is correct
11 Correct 399 ms 7172 KB Output is correct
12 Correct 155 ms 7260 KB Output is correct
13 Incorrect 2 ms 6488 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15568 KB Output is correct
2 Correct 44 ms 19284 KB Output is correct
3 Correct 41 ms 17232 KB Output is correct
4 Correct 41 ms 17744 KB Output is correct
5 Correct 53 ms 18512 KB Output is correct
6 Correct 42 ms 17660 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 8 ms 7160 KB Output is correct
4 Correct 10 ms 7004 KB Output is correct
5 Correct 9 ms 7156 KB Output is correct
6 Correct 8 ms 7004 KB Output is correct
7 Correct 8 ms 7152 KB Output is correct
8 Correct 173 ms 7176 KB Output is correct
9 Correct 179 ms 7260 KB Output is correct
10 Correct 108 ms 7184 KB Output is correct
11 Correct 399 ms 7172 KB Output is correct
12 Correct 155 ms 7260 KB Output is correct
13 Incorrect 2 ms 6488 KB Output isn't correct
14 Halted 0 ms 0 KB -