oj.uz

Submission #922930

# Submission time Handle Problem Language Result Execution time Memory
922930 2024-02-06T10:01:47 Z Andrei_ierdnA Museum (CEOI17_museum) C++17
100 / 100
 205 ms 233724 KB 
#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

#define MAXN 10000
#define INF 1000000000

struct Edge
{
    int a, b, c;
    int other(int node) {
        return (node == a) ? b : a;
    }
};

int n, k, x, i, sz[MAXN+2];
int dpcyc[MAXN+2][MAXN+2], dp[MAXN+2][MAXN+2];
vector<int> nb[MAXN+2];
Edge edges[MAXN+2];

void dfs1(int node)
{
    sz[node] = 1;
    dpcyc[node][1] = dp[node][1] = 0;
    for (auto e : nb[node]) {
        int x = edges[e].other(node);
        int c = edges[e].c;
        if (!sz[x]) {
            dfs1(x);
            for (int i = sz[node]+1; i <= sz[node]+sz[x]; i++) {
                dpcyc[node][i] = dp[node][i] = INF;
            }
            for (int i = sz[node]; i >= 1; i--) {
                for (int j = sz[x]; j >= 1; j--) {
                    dpcyc[node][i+j] = min(dpcyc[node][i+j], dpcyc[node][i] + dpcyc[x][j] + 2*c);
                    dp[node][i+j] = min(dp[node][i+j], dp[node][i] + dpcyc[x][j] + 2*c);
                    dp[node][i+j] = min(dp[node][i+j], dpcyc[node][i] + dp[x][j] + c);
                }
            }
            sz[node] += sz[x];
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k >> x;
    for (i = 1; i < n; i++) {
        cin >> edges[i].a >> edges[i].b >> edges[i].c;
        nb[edges[i].a].push_back(i);
        nb[edges[i].b].push_back(i);
    }
    dfs1(x);
    cout << dp[x][k];
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 100284 KB Output is correct
2 Correct 137 ms 100692 KB Output is correct
3 Correct 202 ms 229904 KB Output is correct
4 Correct 155 ms 140264 KB Output is correct
5 Correct 157 ms 108884 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 100284 KB Output is correct
2 Correct 137 ms 100692 KB Output is correct
3 Correct 202 ms 229904 KB Output is correct
4 Correct 155 ms 140264 KB Output is correct
5 Correct 157 ms 108884 KB Output is correct
6 Correct 138 ms 99924 KB Output is correct
7 Correct 176 ms 175832 KB Output is correct
8 Correct 205 ms 99068 KB Output is correct
9 Correct 177 ms 98984 KB Output is correct
10 Correct 160 ms 99548 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 143 ms 100284 KB Output is correct
7 Correct 137 ms 100692 KB Output is correct
8 Correct 202 ms 229904 KB Output is correct
9 Correct 155 ms 140264 KB Output is correct
10 Correct 157 ms 108884 KB Output is correct
11 Correct 138 ms 99924 KB Output is correct
12 Correct 176 ms 175832 KB Output is correct
13 Correct 205 ms 99068 KB Output is correct
14 Correct 177 ms 98984 KB Output is correct
15 Correct 160 ms 99548 KB Output is correct
16 Correct 138 ms 100792 KB Output is correct
17 Correct 137 ms 100688 KB Output is correct
18 Correct 163 ms 150048 KB Output is correct
19 Correct 185 ms 99180 KB Output is correct
20 Correct 157 ms 99936 KB Output is correct
21 Correct 174 ms 172336 KB Output is correct
22 Correct 137 ms 102380 KB Output is correct
23 Correct 185 ms 99000 KB Output is correct
24 Correct 138 ms 99664 KB Output is correct
25 Correct 198 ms 233724 KB Output is correct