Submission #541222

#	Time	Username	Problem	Language	Result	Execution time	Memory
541222		rainliofficial	Museum (CEOI17_museum)	C++17	0 / 100	597 ms	1048576 KiB

museum

#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 = 10005;
int n, k, x, ss[MAXN], dp[MAXN][MAXN][2], dp2[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=1; atSize<=currSize; atSize++){
                for (int newSize=1; newSize<=ss[i.to]; newSize++){
                    dp2[at][atSize + newSize][0] = min({dp2[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});
                    dp2[at][atSize + newSize][1] = min(dp2[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++){
                    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++){
                    dp2[at][atSize + newSize][0] = dp2[at][atSize + newSize][1] = MAXN;
                    
                }
            }
            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] = MAXN;
            }
            dp2[i][j][0] = dp2[i][j][1] = MAXN;
        }
    }
    subtreeSize(x, -1);
    dfs(x, -1);
    cout << dp[x][k][0] << "\n";
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20