oj.uz

Submission #541268

# Submission time Handle Problem Language Result Execution time Memory
541268 2022-03-22T20:55:06 Z rainliofficial Museum (CEOI17_museum) C++17
100 / 100
 494 ms 784368 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define sz(x) (int)x.size()
#define f first
#define s second

/**
 * The challenge of the problem is to know which edges we want to "backtrack" on (meaning we pass an edge twice). 
 * It is key that we realize the given graph is a tree, which means we can use tree DP. 
 * 
 * Let dp[i][j][0/1] = the min cost to visit j nodes in subtree of i, such that 0 = we don't return back to i, 1 = we return back to i
 */

struct edge{
    int to, c;
};

const int MAXN = 10001;
int n, k, x, ss[MAXN], dp[MAXN][MAXN][2];
vector<edge> arr[MAXN];

void subtreeSize(int at, int par){
    ss[at] = 1;
    for (edge i : arr[at]){
        if (i.to != par){
            subtreeSize(i.to, at);
            ss[at] += ss[i.to];
        }
    }
}

void dfs(int at, int par){
    // try to "tack on" the answer of the children of at
    int currSize = 1; 
    for (edge i : arr[at]){
        if (i.to != par){
            dfs(i.to, at);
            // combine the new subtree with the existing subtree of at
            for (int atSize=currSize; atSize>=1; atSize--){
                for (int newSize=ss[i.to]; newSize>=1; newSize--){
                    if (atSize + newSize > k){
                        continue;
                    }
                    dp[at][atSize + newSize][0] = min({dp[at][atSize + newSize][0], dp[at][atSize][1] + dp[i.to][newSize][0] + i.c, dp[at][atSize][0] + dp[i.to][newSize][1] + 2*i.c});
                    dp[at][atSize + newSize][1] = min(dp[at][atSize + newSize][1], dp[at][atSize][1] + dp[i.to][newSize][1] + 2*i.c);
                }
            }
            // // copy over data
            // for (int atSize=1; atSize<=currSize; atSize++){
            //     for (int newSize=1; newSize<=ss[i.to]; newSize++){
            //         if (atSize + newSize > k){
            //             continue;
            //         }
            //         dp[at][atSize + newSize][0] = min(dp[at][atSize + newSize][0], dp2[at][atSize + newSize][0]);
            //         dp[at][atSize + newSize][1] = min(dp[at][atSize + newSize][1], dp2[at][atSize + newSize][1]);
            //     }
            // }
            // for (int atSize=1; atSize<=currSize; atSize++){
            //     for (int newSize=1; newSize<=ss[i.to]; newSize++){
            //         if (atSize + newSize > k){
            //             continue;
            //         }
            //         dp2[at][atSize + newSize][0] = dp2[at][atSize + newSize][1] = INT_MAX;
                    
            //     }
            // }
            currSize += ss[i.to];
        }
    }
}
int main(){
    cin.tie(0); ios_base::sync_with_stdio(0);
    // freopen("file.in", "r", stdin);
    // freopen("file.out", "w", stdout);
    cin >> n >> k >> x;
    x--;
    for (int i=0; i<n-1; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        arr[a].push_back({b, c});
        arr[b].push_back({a, c});
    }
    for (int i=0; i<MAXN; i++){
        for (int j=0; j<MAXN; j++){
            if (j > 1){
                dp[i][j][0] = dp[i][j][1] = INT_MAX;
            }
            // dp2[i][j][0] = dp2[i][j][1] = INT_MAX;
        }
    }
    subtreeSize(x, -1);
    dfs(x, -1);
    cout << dp[x][k][0] << "\n";
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 783492 KB Output is correct
2 Correct 334 ms 783436 KB Output is correct
3 Correct 353 ms 783488 KB Output is correct
4 Correct 336 ms 783352 KB Output is correct
5 Correct 346 ms 783476 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 783896 KB Output is correct
2 Correct 404 ms 783804 KB Output is correct
3 Correct 399 ms 784232 KB Output is correct
4 Correct 399 ms 783948 KB Output is correct
5 Correct 392 ms 783852 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 783896 KB Output is correct
2 Correct 404 ms 783804 KB Output is correct
3 Correct 399 ms 784232 KB Output is correct
4 Correct 399 ms 783948 KB Output is correct
5 Correct 392 ms 783852 KB Output is correct
6 Correct 398 ms 783972 KB Output is correct
7 Correct 398 ms 784072 KB Output is correct
8 Correct 412 ms 783820 KB Output is correct
9 Correct 410 ms 783924 KB Output is correct
10 Correct 396 ms 783872 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 783492 KB Output is correct
2 Correct 334 ms 783436 KB Output is correct
3 Correct 353 ms 783488 KB Output is correct
4 Correct 336 ms 783352 KB Output is correct
5 Correct 346 ms 783476 KB Output is correct
6 Correct 398 ms 783896 KB Output is correct
7 Correct 404 ms 783804 KB Output is correct
8 Correct 399 ms 784232 KB Output is correct
9 Correct 399 ms 783948 KB Output is correct
10 Correct 392 ms 783852 KB Output is correct
11 Correct 398 ms 783972 KB Output is correct
12 Correct 398 ms 784072 KB Output is correct
13 Correct 412 ms 783820 KB Output is correct
14 Correct 410 ms 783924 KB Output is correct
15 Correct 396 ms 783872 KB Output is correct
16 Correct 411 ms 783820 KB Output is correct
17 Correct 444 ms 784144 KB Output is correct
18 Correct 404 ms 784308 KB Output is correct
19 Correct 422 ms 783960 KB Output is correct
20 Correct 409 ms 784136 KB Output is correct
21 Correct 465 ms 784280 KB Output is correct
22 Correct 462 ms 784204 KB Output is correct
23 Correct 494 ms 784060 KB Output is correct
24 Correct 459 ms 784076 KB Output is correct
25 Correct 467 ms 784368 KB Output is correct