Submission #1128361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128361		trMatherz	Museum (CEOI17_museum)	C++20	0 / 100	149 ms	6208 KiB

museum

#include <iostream> 
 
 
// #include <fstream>
// std::ifstream cin ("boarding.in");
// std::ofstream cout ("boarding.out");
 
 
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <stack>
#include <tuple>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>
#include <chrono>
#include <bitset>
#include <complex>
#include <tuple> 
 

using namespace std;
using namespace __gnu_pbds;

 
typedef long long ll;
template <typename T, typename U>
bool emin(T &a, const U &b) { return b < a ? a = b, true : false; }
template <typename T, typename U>
bool emax(T &a, const U &b) { return b > a ? a = b, true : false; }
template <class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef uint64_t hash_t;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
const ll M = (1LL << 61) - 1;
const ll B = uniform_int_distribution<ll>(0, M - 1)(rng);
__int128 mul(ll a, ll b) { return (__int128)a * b; }
__int128 add(ll a, ll b) { return (__int128)a + b; }
ll mod_mul(ll a, ll b) { return mul(a, b) % M; }
ll mod_add(ll a, ll b) { return add(a, b) % M; }

const ll inf = (ll) 1e18; 
int n, k, s;
vector<vector<pair<ll, ll>>> a; 
vector<vector<vector<ll>>> dp; 
vector<ll> comp(vector<ll> a, vector<ll> b, ll x) {
    vector<ll> c(a.size() + b.size() - 1, inf); 
    for(int i = 0; i < a.size(); i++) {
        for(int j = 0; j < b.size(); j++) {
            emin(c[i + j], a[i] + b[j] + (i || j ? x : 0)); 
        }
    }
    for(int i = 0; i < a.size(); i++) emin(c[i], a[i]); 
    for(int i = 0; i < b.size(); i++) emin(c[i], b[i]); 
    return c; 
}
void go(int x, int y = -1) {
    dp[0][x] = {0, 0}; 
    dp[1][x] = {0, 0}; 
    for(auto &u : a[x]) {
        if(u.first == y) continue; 
        go(u.first, x);
        dp[1][x] = comp(dp[1][x], dp[0][u.first], u.second * 2); 
        auto temp = comp(dp[0][x], dp[1][u.first], u.second); 
        for(int i = 0; i < dp[1][x].size(); i++) emin(dp[1][x][i], temp[i]); 
        dp[0][x] = comp(dp[0][x], dp[0][u.first], u.second * 2); 
    }
    
}
int main() {
    cin >> n >> k >> s; s--;
    a = vector<vector<pair<ll, ll>>>(n); 
    dp = vector<vector<vector<ll>>>(2, vector<vector<ll>>(n)); 
    for(int i = 0; i < n - 1; i++) {
        ll x, y, z; 
        cin >> x >> y >> z; 
        x--, y--; 
        a[x].push_back({y, z}), a[y].push_back({x, z});
    }
    go(s); 
    cout << dp[1][s][k]; 
}

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