oj.uz

Submission #780505

# Submission time Handle Problem Language Result Execution time Memory
780505 2023-07-12T09:38:16 Z thefless Museum (CEOI17_museum) C++17
100 / 100
 278 ms 284904 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 3 ms 7252 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9444 KB Output is correct
2 Correct 13 ms 9556 KB Output is correct
3 Correct 28 ms 14500 KB Output is correct
4 Correct 18 ms 12148 KB Output is correct
5 Correct 15 ms 11236 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9444 KB Output is correct
2 Correct 13 ms 9556 KB Output is correct
3 Correct 28 ms 14500 KB Output is correct
4 Correct 18 ms 12148 KB Output is correct
5 Correct 15 ms 11236 KB Output is correct
6 Correct 12 ms 9044 KB Output is correct
7 Correct 21 ms 14056 KB Output is correct
8 Correct 34 ms 8428 KB Output is correct
9 Correct 26 ms 8412 KB Output is correct
10 Correct 13 ms 8532 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 3 ms 7252 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 13 ms 9444 KB Output is correct
7 Correct 13 ms 9556 KB Output is correct
8 Correct 28 ms 14500 KB Output is correct
9 Correct 18 ms 12148 KB Output is correct
10 Correct 15 ms 11236 KB Output is correct
11 Correct 12 ms 9044 KB Output is correct
12 Correct 21 ms 14056 KB Output is correct
13 Correct 34 ms 8428 KB Output is correct
14 Correct 26 ms 8412 KB Output is correct
15 Correct 13 ms 8532 KB Output is correct
16 Correct 30 ms 10452 KB Output is correct
17 Correct 76 ms 11440 KB Output is correct
18 Correct 54 ms 36896 KB Output is correct
19 Correct 66 ms 8464 KB Output is correct
20 Correct 27 ms 9160 KB Output is correct
21 Correct 198 ms 159104 KB Output is correct
22 Correct 102 ms 12124 KB Output is correct
23 Correct 211 ms 8780 KB Output is correct
24 Correct 93 ms 10172 KB Output is correct
25 Correct 278 ms 284904 KB Output is correct