oj.uz

답안 #873359

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -