oj.uz

Submission #541263

# Submission time Handle Problem Language Result Execution time Memory
541263 2022-03-22T20:46:28 Z rainliofficial Museum (CEOI17_museum) C++17
20 / 100
 236 ms 16920 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, MAXK = 101;
int n, k, x, ss[MAXN], dp[MAXN][MAXK][2], dp2[MAXN][MAXK][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] = 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<MAXK; 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 8 ms 16464 KB Output is correct
2 Correct 8 ms 16340 KB Output is correct
3 Correct 8 ms 16340 KB Output is correct
4 Correct 8 ms 16332 KB Output is correct
5 Correct 8 ms 16284 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 236 ms 16920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 236 ms 16920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16464 KB Output is correct
2 Correct 8 ms 16340 KB Output is correct
3 Correct 8 ms 16340 KB Output is correct
4 Correct 8 ms 16332 KB Output is correct
5 Correct 8 ms 16284 KB Output is correct
6 Incorrect 236 ms 16920 KB Output isn't correct
7 Halted 0 ms 0 KB -