Submission #1307020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307020		pasta	Museum (CEOI17_museum)	C++20	100 / 100	490 ms	785288 KiB

museum

//Oh? You're Approaching Me?
 
#include <bits/stdc++.h>
using namespace std;
//  
// #define int long long
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
 
 
// #pragma GCC optimize("O3,unroll-loops")
#define migmig     		    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          		push_back
#define F           		first
#define S           		second
#define SZ(x)       		ll((x).size())
#define all(x)      		(x).begin(), (x).end()
#define cl          		clear
#define endl        		'\n'
#define deb(x)    			cerr << #x << " = " << x << '\n'
#define dokme(x)			{cout << x << endl; return;}
#define wtf					cout << "[ahaaaaaaaaaaaaaaaa]" << endl;
 
const int maxn = 1e4 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9 + 5;
const int LOG = 21;
const int sq = 320;
// #define mid		((l + r) / 2)
// #define lc		(id * 2)
// #define rc		(lc + 1)
//g++ main.cpp -o main && main.exe

int n, k, x, dp[maxn][maxn], pd[maxn][maxn], sz[maxn];
vector<pii> G[maxn];


void dfs(int v, int p) {
    dp[v][1] = pd[v][1] = 0;
    sz[v] = 1;
    for (auto [u, w]: G[v]) {
        if (u == p)
            continue;
        dfs(u, v);
        for (int x = sz[v]; x >= 1; x--) {
            for (int y = sz[u]; y >= 1; y--) {
                pd[v][x + y] = min(pd[v][x + y], pd[v][x] + pd[u][y] + 2 * w);
                dp[v][x + y] = min(dp[v][x + y], pd[v][x] + dp[u][y] + w);
                dp[v][x + y] = min(dp[v][x + y], dp[v][x] + pd[u][y] + 2 * w);
            }
        }
        sz[v] += sz[u];
    }
}

signed main() {
    cin >> n >> k >> x;
    for (int i = 1; i < n; i++) {
        int v, u, w;
        cin >> v >> u >> w;
        G[v].pb({u, w});
        G[u].pb({v, w});
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = pd[i][j] = inf;
        }
    }
    dfs(x, 0);
    // cout << pd[x][k] << '\n';
    cout << min(pd[x][k], dp[x][k]) << '\n';
}

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