oj.uz

Submission #873442

# Submission time Handle Problem Language Result Execution time Memory
873442 2023-11-15T05:52:49 Z sleepntsheep Paths (RMI21_paths) C++17
48 / 100
 328 ms 19028 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];

namespace sub123
{
    ll dp[1001][101];
    int sz[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);
        dfs1(u, u);
        return dp[u][k];
    }
};

namespace sub5
{
    ll dp2[N], dp3[N], dp4[N];
    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);
        }
    }
};

namespace sub4
{
    int tin[N], tout[N], timer = 0;
    ll t[N<<1], lz[N<<1], rt[N];

    void dfs1(int u, int p)
    {
        tin[u] = timer++;
        for (auto [w, v] : g[u]) if (v != p) rt[v] = rt[u] + w, dfs1(v, u);
        tout[u] = timer - 1;
    }

};

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)
    {
        sub5::dfs2(1, 1);
        sub5::dfs3(1, 1);
        for (int i = 1; i <= n; ++i) cout << max(sub5::dp2[i], sub5::dp4[i]) << '\n';
    }
    else if (n <= 1002)
    {
        for (int i = 1; i <= n; ++i) cout << sub123::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 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 7 ms 8536 KB Output is correct
4 Correct 6 ms 8688 KB Output is correct
5 Correct 7 ms 8540 KB Output is correct
6 Correct 6 ms 8540 KB Output is correct
7 Correct 6 ms 8540 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 7 ms 8536 KB Output is correct
4 Correct 6 ms 8688 KB Output is correct
5 Correct 7 ms 8540 KB Output is correct
6 Correct 6 ms 8540 KB Output is correct
7 Correct 6 ms 8540 KB Output is correct
8 Correct 165 ms 8724 KB Output is correct
9 Correct 157 ms 8792 KB Output is correct
10 Correct 106 ms 8540 KB Output is correct
11 Correct 328 ms 8712 KB Output is correct
12 Correct 148 ms 8720 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 7 ms 8536 KB Output is correct
4 Correct 6 ms 8688 KB Output is correct
5 Correct 7 ms 8540 KB Output is correct
6 Correct 6 ms 8540 KB Output is correct
7 Correct 6 ms 8540 KB Output is correct
8 Correct 165 ms 8724 KB Output is correct
9 Correct 157 ms 8792 KB Output is correct
10 Correct 106 ms 8540 KB Output is correct
11 Correct 328 ms 8712 KB Output is correct
12 Correct 148 ms 8720 KB Output is correct
13 Incorrect 2 ms 6492 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 53 ms 17492 KB Output is correct
2 Correct 54 ms 19028 KB Output is correct
3 Correct 39 ms 17128 KB Output is correct
4 Correct 44 ms 17784 KB Output is correct
5 Correct 42 ms 18264 KB Output is correct
6 Correct 45 ms 17344 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 7 ms 8536 KB Output is correct
4 Correct 6 ms 8688 KB Output is correct
5 Correct 7 ms 8540 KB Output is correct
6 Correct 6 ms 8540 KB Output is correct
7 Correct 6 ms 8540 KB Output is correct
8 Correct 165 ms 8724 KB Output is correct
9 Correct 157 ms 8792 KB Output is correct
10 Correct 106 ms 8540 KB Output is correct
11 Correct 328 ms 8712 KB Output is correct
12 Correct 148 ms 8720 KB Output is correct
13 Incorrect 2 ms 6492 KB Output isn't correct
14 Halted 0 ms 0 KB -