Submission #922262

#	Time	Username	Problem	Language	Result	Execution time	Memory
922262		phong	Museum (CEOI17_museum)	C++17	0 / 100	7 ms	9816 KiB

museum

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

#define ll long long
const int nmax = 2e5 + 100;
const ll oo = 1e18, base = 311;
const int lg = 19, M = 10;
const ll mod = 1e9 + 7;
#define pii pair<ll, int>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' ';
using namespace std;

ll n, k, x;
ll c[nmax], d[nmax], h[nmax], par[nmax];
struct node{
    ll u, h, w;
    friend bool operator < (const node& a, const node& b){
        if(a.h == b.h) return a.w < b.w;
        return a.h > b.h;
    }
};
multiset<node> mt;
vector<pii> adj[nmax];

void dfs(int u, int p){
    bool ok = 0;

    for(auto [w, v] : adj[u]){
        if(v == p) continue;
        d[v] = d[u] + w;
        h[v] = w;
        par[v] = u;

        ok = 1;
        dfs(v, u);
    }
    if(!ok){
        mt.insert({u, h[u], d[u]});
    }
}
void update(){
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> k >> x;
    k = n - k;
    for(int i = 1, u, v, w; i < n; ++i){
        cin >> u >> v >> w;
        adj[u].push_back({w, v});
        adj[v].push_back({w, u});
    }
    dfs(x, -1);
    while(k > 0){
        node tmp = *mt.begin();
        int u = tmp.u;
        c[u] = 1;
        mt.erase({u, h[u], d[u]});
        u = par[u];
        mt.insert({u, h[u], d[u]});
        --k;
    }
    ll sum = 0, cur = 0;
    for(int i = 1; i <= n; ++i){
        if(!c[i]){
            sum += h[i];
            cur = max(cur, (ll)d[i]);
        }
    }
    cout << sum * 2 - cur;

}
/*
4
1 2 3 4
10 0 1 0
5
5 3 5 3 5
10 1 20 1 20
*/

Compilation message (stderr)

museum.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main(){
      | ^~~~

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