Submission #1236419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236419		iiiindex	Museum (CEOI17_museum)	C++20	0 / 100	67 ms	144448 KiB

museum

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()



using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
constexpr int inf = 1e9 + 7;
constexpr ll INF = 1e18 + 14;
constexpr int mod = 1e9 + 7;
constexpr int maxn = 3e5 + 100;
constexpr int maxm = 2e6 + 100;
constexpr db eps = 1e-6;

ll inv2, inv3;

inline char get(void) {
    static char buf[1 << 19], *p1 = buf, *p2 = buf;
    if (p1 == p2) {
        p2 = (p1 = buf) + fread(buf, 1, 1 << 19, stdin);
        if (p1 == p2) return EOF;
    }
    return *p1++;
}

template<typename T>
inline void read(T &x) {
    x = 0; static char c; bool minus = false;
    for (; !(c >= '0' && c <= '9'); c = get()) if (c == '-') minus = true;
    for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = get()); if (minus) x = -x;
}

template<typename T>
void add(T& x, const T& y) {if((x += y) >= mod) x -= mod;}
template<typename T>
void dec(T& x, const T& y) {if((x -= y) < 0) x += mod;}
template<typename T>
void cmax(T& x, const T& y) {if(y > x) x = y;}
template<typename T>
void cmin(T& x, const T& y) {if(y < x) x = y;}

ll qpow(ll x, ll a){
    ll base = x, rt = 1;
    while(a){
        if(a & 1) rt *= base, rt %= mod;
        base *= base, base %= mod;
        a >>= 1;
    }
    return rt;
}

ll inv(ll a){
    if(a < 0) a += mod;
    return qpow(a, mod - 2);
}

int lowbit(int x){
    return x & (-x);
}

ll lcm(ll a, ll b){
    ll g = __gcd(a, b);
    return a / g * b;
}

struct custom_hash {
   static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};


vector<ll> fac, ifac;
 
void init_fac(){
    fac.resize(maxn), ifac.resize(maxn);
    fac[0] = fac[1] = 1;
    for(int i = 2; i < maxn; i++) fac[i] = fac[i - 1] * i % mod;
    ifac[maxn - 1] = inv(fac[maxn - 1]);
    for(int i = maxn - 2; i >= 0; i--) ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
 
ll C(int n, int m){
    return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

vector<int> prime, np, divi;

void init_prime(){
    np.resize(maxm); divi.resize(maxm);
    for(int i = 2; i < maxm; i++){
        if(!np[i]) {prime.push_back(i); divi[i] = i;}
        for(auto v: prime){
            if(v * i >= maxm) break;
            np[v * i] = 1; divi[v * i] = v;
            if(i % v == 0) break;
        }
    }
}

void init(){
    
}

void solve() {
    int n, k, rt; cin >> n >> k >> rt;
    vector e(n + 1, vector(0, pair(0, 0)));
    for (int i = 1; i < n; i++) {
        int u, v, w; cin >> u >> v >> w;
        e[u].emplace_back(v, w); e[v].emplace_back(u, w);
    }

    vector dp(n + 1, vector(k + 1, array<int, 2>{inf, inf}));

    auto dfs = [&](auto&& self, int u, int fa) -> int {
        int siz = 1;
        dp[u][1] = {0, 0};
        for (auto [v, w]: e[u]) {
            if (v == fa) continue;
            auto csiz = self(self, v, u);
            for (int i = min(siz + csiz, k); i > 0; i--) for (int j = min(csiz, i); j >= max(1, i - siz); j--) {
                // cerr << dp[u][i][0] << endl;
                cmin(dp[u][i][0], dp[u][i - j][0] + dp[v][j][0] + 2 * w);
                cmin(dp[u][i][1], dp[u][i - j][0] + dp[v][j][1] + w);
                cmin(dp[u][i][1], dp[u][i - j][1] + dp[v][j][0] + 2 * w);
                // cerr << i << ' ' << dp[u][i][0] << ' ' << dp[u][i][1] << endl;
                // cerr << i << ' ' << j << ' ' << dp[u][i - j][0] << ' ' << dp[v][j][0] << endl;
            }
            siz += csiz;
        }
        return siz;
    };
    dfs(dfs, rt, 0);

    cout << dp[rt][k][1] << endl;
    
}

int main(){
    // cerr << inv(2) << endl;
    // clock_t st = clock(), ed;
    #ifndef ONLINE_JUDGE
        freopen("1.in", "r", stdin);
        freopen("my.out", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // srand(114514);
    init();
    int t = 1;
    cout << setprecision(3) << fixed;
    cerr << setprecision(2) << fixed;
    // cin >> t;
    // read(t);
    while(t--){
        solve();
    }
    // ed = clock();
    // double endtime=(double)(ed-st)/CLOCKS_PER_SEC;
    // cout<<"Total time:"<<endtime<<endl;
    // system("pause");
    return 0;
}

Compilation message (stderr)

museum.cpp: In function 'int main()':
museum.cpp:153:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |         freopen("1.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
museum.cpp:154:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |         freopen("my.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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