oj.uz

Submission #922262

# Submission time Handle Problem Language Result Execution time Memory
922262 2024-02-05T10:04:44 Z phong Museum (CEOI17_museum) C++17
0 / 100
 7 ms 9816 KB 
#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

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 9816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 9816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8796 KB Output isn't correct
2 Halted 0 ms 0 KB -