Submission #780505

#	Time	Username	Problem	Language	Result	Execution time	Memory
780505		thefless	Museum (CEOI17_museum)	C++17	100 / 100	278 ms	284904 KiB

museum

#include<bits/stdc++.h>
using namespace std;
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define Times (1.0 * clock() / CLOCKS_PER_SEC)
#define fi first
#define base 31
#define sz(x) (int)(x).size()
#define se second
#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()

#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
#define task "name" 
#define tsk "" 

const int oo = 1e9 + 7;
const ll loo = (ll)1e18 + 7;
const int MOD = 1e9 + 7;
const int MOD2 = 1e9 + 696969;
const int N = 1e5 + 3;
const int BASE = 10;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}

int n , k , x;
bool vst[N];
vector<ll> dp[N][2];
vector<pii> adj[N];
int fin[N];
void cal_fin(int u , int par){
    fin[u] = 1;
    for(auto x : adj[u]){
        int v = x.se;
        if(v == par) continue;
        cal_fin(v , u);
        fin[u] += fin[v];
    }
}
 void dfs(int u , int par){
    dp[u][0].assign(min(k , fin[u]) + 2 , loo);
    dp[u][1].assign(min(k , fin[u]) + 2 , loo);
    dp[u][0][0] = dp[u][0][1] = dp[u][1][0] = dp[u][1][1] = 0;
    int total = 1;
    for(auto x : adj[u]){
        int v = x.se;
        int w = x.fi;
        if(v == par) continue;
        dfs(v , u);
        total += fin[v];
        for(int i = total ; i >= 2 ; i--){
            if(i > k) continue;
            for(int j = max(0 , i - total + fin[v]) ; j <= min(i , fin[v]) ; j++){
                minimize(dp[u][0][i] , dp[u][0][i - j] + dp[v][1][j] + 2 * w);
                minimize(dp[u][0][i] , dp[u][1][i - j] + dp[v][0][j] + w);
                minimize(dp[u][1][i] , dp[u][1][i - j] + dp[v][1][j] + 2 * w);
            }
        }
    }
 } 
void Solve(){
    cin >> n >> k >> x;
    for(int i = 1 ; i < n ; i++){
        int u , v , w;
        cin >> u >> v >> w;
        adj[u].pb({w , v});
        adj[v].pb({w , u});
    }
    cal_fin(x , -1);
    dfs(x , -1);
    cout << dp[x][0][k];
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    file(task);
    file(tsk);
    int T = 1;
    // cin >> T;
    while(T--)
    {
        Solve();
    }
    cerr << "Time elapsed: " << Times << " s.\n";
    return 0;
}

Compilation message (stderr)

museum.cpp: In function 'int main()':
museum.cpp:16:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:81:5: note: in expansion of macro 'file'
   81 |     file(task);
      |     ^~~~
museum.cpp:16:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:81:5: note: in expansion of macro 'file'
   81 |     file(task);
      |     ^~~~
museum.cpp:16:125: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
      |                                                                                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:81:5: note: in expansion of macro 'file'
   81 |     file(task);
      |     ^~~~
museum.cpp:16:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:82:5: note: in expansion of macro 'file'
   82 |     file(tsk);
      |     ^~~~
museum.cpp:16:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:82:5: note: in expansion of macro 'file'
   82 |     file(tsk);
      |     ^~~~
museum.cpp:16:125: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
      |                                                                                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:82:5: note: in expansion of macro 'file'
   82 |     file(tsk);
      |     ^~~~

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