Submission #998595

#	Time	Username	Problem	Language	Result	Execution time	Memory
998595		NoLove	Museum (CEOI17_museum)	C++14	0 / 100	156 ms	6800 KiB

museum

/**
 *    author : Lăng Trọng Đạt
 *    created: 14-06-2024 
**/
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN = 1e4 + 5;
const int INF = 1e18;
int g[MAXN];
vector<pair<int, int>> adj[MAXN];
int n;

vector<int> dp[MAXN][2]; // dp[i][j][t]: thời gian tối thiểu để thăm quan j phòng phân biệt khi đi từ node i
// t = 0: đi và đã trở về i
// t = 1: đi và dừng tại địa điểm thứ j
vector<int> min_time(vector<int>& a, vector<int>& b, int w) {
    vector<int> res(a.size() + b.size() - 1, INF);
    for (int i = 0; i < a.size(); i++)
        for (int j = 0; j < b.size(); j++)
            res[i + j] = min(res[i + j], a[i] + b[j] + (j > 0 ?  w : 0));
    return res;
}
void dfs(int v, int prv) {
    dp[v][0] = {0, 0};
    dp[v][1] = {0, 0};
    vector<pair<int, int>> chill;
    vector<int> suf = {0};
    vector<vector<int>> pref;
    pref.push_back(dp[v][1]);
    for (auto[u, w] : adj[v]) {
        if (u == prv) continue;
        chill.push_back({u, w});
        // db(v, u)
        dfs(u, v);
        dp[v][0] = min_time(dp[v][0], dp[u][0], 2*w);
        pref.push_back(dp[v][0]);
    }   
    pref.pop_back();
    // db(v, chill)
    for (int i = chill.size() - 1; i >= 0; i--) {
        int u = chill[i].first, w = chill[i].second;
        // db(i, pref.size())
        vector<int> tmp = min_time(pref.back(), suf, 0);
        dp[u][1][0] = INF;
        vector<int> tmp2 = min_time(tmp, dp[u][1], w);
        for (int j = 1; j < tmp2.size(); j++) {
            if (j < dp[v][1].size()) dp[v][1][j] = min(dp[v][1][j], tmp2[j]);
            else dp[v][1].push_back(tmp2[j]);
        }
        // if (v == 1 && dp[v][1].size() > 4 && dp[v][1][4] == 6) {
        //     db(u, w, suf, pref.back(), dp[u][1])
        //     db(tmp)
        //     db(tmp2)
        //     exit(0);
        // }
        suf = min_time(suf, dp[u][1], 2*w);
        pref.pop_back();
    }
    // db(dp[v][0])
    // db(dp[v][1])
}
main() {
    // freopen("hi.inp", "r", stdin);

    int k, root;
    cin >> n >> k >> root;
    int a, b, c;
    for (int i = 1; i < n; i++) {
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }   
    dfs(root, -1);  

    // db("fuck")
    cout << dp[root][1][k];
}

Compilation message (stderr)

museum.cpp: In function 'std::vector<long long int> min_time(std::vector<long long int>&, std::vector<long long int>&, long long int)':
museum.cpp:20:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
museum.cpp:21:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for (int j = 0; j < b.size(); j++)
      |                         ~~^~~~~~~~~~
museum.cpp: In function 'void dfs(long long int, long long int)':
museum.cpp:32:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |     for (auto[u, w] : adj[v]) {
      |              ^
museum.cpp:48:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for (int j = 1; j < tmp2.size(); j++) {
      |                         ~~^~~~~~~~~~~~~
museum.cpp:49:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             if (j < dp[v][1].size()) dp[v][1][j] = min(dp[v][1][j], tmp2[j]);
      |                 ~~^~~~~~~~~~~~~~~~~
museum.cpp: At global scope:
museum.cpp:64:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   64 | main() {
      | ^~~~

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