제출 #1291422

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291422		nhan0123456	Museum (CEOI17_museum)	C++20	100 / 100	278 ms	360268 KiB

museum

#include <bits/stdc++.h>
using namespace std;
bool memory1;

typedef long long ll;
typedef unsigned long long ull;
typedef double dbe;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<ll> vll;
typedef vector<int> vii;

#define openFile(name) freopen((name ".inp"), "r", stdin), freopen((name ".out"), "w", stdout)
#define FOR(i, a, b, x) for (ll i = (a); i <= (b); i += (x))
#define ROF(i, a, b, x) for (ll i = (a); i >= (b); i += (x))
#define fi first
#define se second
#define MASK(x) (1LL << (x))
#define getBit(mask, i) (((mask) >> (i)) & 1)
#define BitOn(mask) (__builtin_popcountll(mask))

const int maxN = 1e4 + 5;
//const ll maxBit = MASK(8) + 2;
const ll LOG = 20;
const ll INF18 = 1e18;
const int INF9 = 1e9;
//const ll INF3f = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 1e9 + 7;

//////////////////////////////////////////////
/////////////////nhan0123456//////////////////
//////////////////////////////////////////////

ll n, K, X;
int sz[maxN];

ll dp[2][maxN][maxN];
ll tmp[2][maxN];
vector<pll> adj[maxN];

void dfs(int u, int pre) {
    sz[u] = 1;

    for (pll &p : adj[u]) if (p.se != pre) {
        dfs(p.se, u);
        sz[u] += sz[p.se];
    }

    // tao tmp;
    tmp[0][0] = tmp[1][0] = 0;
    FOR (i, 1, sz[u], 1) tmp[0][i] = tmp[1][i] = INF9;

    int knapSize = 0;
    for (pll &p : adj[u]) if (p.se != pre) {
        int v, w;
        tie(w, v) = p;
        ROF (pre, knapSize, 0, -1) {
            FOR (cur, 1, sz[v], 1) {
                int sum = pre + cur;
                /*
                    di vao v roi dung tai v
                    di vao v roi dung tai x
                    di vao v roi dung tai v
                */
                tmp[0][sum] = min(tmp[0][sum], tmp[0][pre] + dp[0][v][cur] + 2 * w);
                tmp[1][sum] = min(tmp[1][sum], tmp[0][pre] + dp[1][v][cur] + w);
                tmp[1][sum] = min(tmp[1][sum], tmp[1][pre] + dp[0][v][cur] + 2 * w);
            }
        }
        knapSize += sz[v];
    }
    FOR (i, 0, sz[u] - 1, 1) {
        dp[0][u][i + 1] = tmp[0][i];
        dp[1][u][i + 1] = tmp[1][i];
    }
}

ll Solve() {
    /*
        root = x;
        bien doi bai toan thanh la di tu x ve x di qua K dinh phan biet
        goi dp u j la tong thoi gian de tham j dinh trong cay con goc u
        va quay lai u

        v1, v2, .. ,vt la con truc tiep cua u
        -> dp u j = min (sum(dp vi si) + (si>0 * 2wi)), voi s1 + s2 + .. + st = k - 1

        goi tmp i j la tong chi phi neu chon j dinh phan biet o i con dau tien voi 1 <= i <= t
        tmp i j = min tmp i - 1 j - c + dp vi, c + c>0 * 2 * wi

        -> dp 0 la di ve u
        -> dp 0 la di ve u

    */
    dfs(X, X);
    return dp[1][X][K];
}

void input() {
    cin >> n >> K >> X;
    int u, v, w;
    FOR (i, 2, n, 1) {
        cin >> u >> v >> w;
        adj[u].emplace_back(w, v);
        adj[v].emplace_back(w, u);
    }
    cout << Solve();
}

int main() {
    //openFile("temp");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    input();

    //bool memory2;
    //cerr << "\n\n\nTime: "<< 1000.0 * clock() / CLOCKS_PER_SEC << " ms";
    //cerr << "\n\n\nMemory: "<< abs(&memory1 - &memory2) * 1.0 / MASK(20) <<" MB";

    return 0;
}

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