oj.uz

Submission #873358

# Submission time Handle Problem Language Result Execution time Memory
873358 2023-11-14T23:15:53 Z sleepntsheep Paths (RMI21_paths) C++17
36 / 100
 407 ms 14676 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 (n <= 1002)
    {
        for (int i = 1; i <= n; ++i) cout << oneroot(i) << '\n';
    }
    else if (n <= 2000)
    {
    }
    else if (k == 1)
    {
        dfs2(0, 0);
        dfs3(0, 0);
        for (int i = 1; i <= n; ++i) cout << max(dp2[i], dp4[i]) << '\n';
    }
    else
    {
    }

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 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 7004 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 8 ms 7004 KB Output is correct
4 Correct 9 ms 7004 KB Output is correct
5 Correct 10 ms 7412 KB Output is correct
6 Correct 9 ms 7016 KB Output is correct
7 Correct 9 ms 7004 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 8 ms 7004 KB Output is correct
4 Correct 9 ms 7004 KB Output is correct
5 Correct 10 ms 7412 KB Output is correct
6 Correct 9 ms 7016 KB Output is correct
7 Correct 9 ms 7004 KB Output is correct
8 Correct 185 ms 7160 KB Output is correct
9 Correct 187 ms 7504 KB Output is correct
10 Correct 113 ms 7168 KB Output is correct
11 Correct 407 ms 7176 KB Output is correct
12 Correct 176 ms 7180 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 8 ms 7004 KB Output is correct
4 Correct 9 ms 7004 KB Output is correct
5 Correct 10 ms 7412 KB Output is correct
6 Correct 9 ms 7016 KB Output is correct
7 Correct 9 ms 7004 KB Output is correct
8 Correct 185 ms 7160 KB Output is correct
9 Correct 187 ms 7504 KB Output is correct
10 Correct 113 ms 7168 KB Output is correct
11 Correct 407 ms 7176 KB Output is correct
12 Correct 176 ms 7180 KB Output is correct
13 Incorrect 2 ms 6488 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 14676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 8 ms 7004 KB Output is correct
4 Correct 9 ms 7004 KB Output is correct
5 Correct 10 ms 7412 KB Output is correct
6 Correct 9 ms 7016 KB Output is correct
7 Correct 9 ms 7004 KB Output is correct
8 Correct 185 ms 7160 KB Output is correct
9 Correct 187 ms 7504 KB Output is correct
10 Correct 113 ms 7168 KB Output is correct
11 Correct 407 ms 7176 KB Output is correct
12 Correct 176 ms 7180 KB Output is correct
13 Incorrect 2 ms 6488 KB Output isn't correct
14 Halted 0 ms 0 KB -