oj.uz

Submission #884456

# Submission time Handle Problem Language Result Execution time Memory
884456 2023-12-07T11:48:56 Z Peter2017 Museum (CEOI17_museum) C++14
100 / 100
 321 ms 785316 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pill pair<int,ll>
#define mem(a, b) memset(a, b, sizeof(a))
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define name "test"

using namespace std;

const int N = 1e4 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;

template <typename T1, typename T2> bool maxi(T1 &a, T2 b){if (a < b){a = b; return 1;} return 0;}
template <typename T1, typename T2> bool mini(T1 &a, T2 b){if (a > b){a = b; return 1;} return 0;}

int n;
int rooms;
int root;
int sz[N];
int g[N][2];
int f[N][N][2];
vector <pii> adj[N];

void load(){
    cin.tie(0)->sync_with_stdio(0);
    if (fopen(name".inp", "r")){
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }
}

void input(){
    cin >> n >> rooms >> root;
    for (int i = 1; i < n; i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
}

void combine(int u, int v, int w){
    for (int i = 0; i <= min(rooms, sz[u] + sz[v]); i++)
        for (int j = 0; j <= 1; j++)
            g[i][j] = mod;
    for (int i = 1; i <= min(rooms, sz[u]); i++)
        for (int j = 0; j <= min(rooms - i, sz[v]); j++){
                mini(g[i + j][0], f[u][i][1] + f[v][j][0] + w);
                mini(g[i + j][0], f[u][i][0] + f[v][j][1] + 2 * w);
                mini(g[i + j][1], f[u][i][1] + f[v][j][1] + 2 * w);
        }
    for (int i = 1; i <= min(rooms, sz[u] + sz[v]); i++)
        for (int j = 0; j <= 1; j++)
            mini(f[u][i][j], g[i][j]);
}

void dfs(int u, int pre){
    sz[u] = 1;
    f[u][1][0] = 0;
    f[u][1][1] = 0;
    for (auto it : adj[u]){
        int v = it.fi;
        int w = it.se;
        if (v != pre){
            dfs(v, u);
            combine(u, v, w);
            sz[u] += sz[v];
        }
    }
}

void solve(){
    mem(f, 0x3f);
    dfs(root, root);
    cout << f[root][rooms][0];
}

int main(){
    load();
    input();
    solve();
}

Compilation message

museum.cpp: In function 'void load()':
museum.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 784212 KB Output is correct
2 Correct 123 ms 784112 KB Output is correct
3 Correct 120 ms 784188 KB Output is correct
4 Correct 120 ms 784208 KB Output is correct
5 Correct 121 ms 784228 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 784464 KB Output is correct
2 Correct 125 ms 784724 KB Output is correct
3 Correct 126 ms 784912 KB Output is correct
4 Correct 123 ms 784836 KB Output is correct
5 Correct 126 ms 784788 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 784464 KB Output is correct
2 Correct 125 ms 784724 KB Output is correct
3 Correct 126 ms 784912 KB Output is correct
4 Correct 123 ms 784836 KB Output is correct
5 Correct 126 ms 784788 KB Output is correct
6 Correct 125 ms 784724 KB Output is correct
7 Correct 129 ms 784816 KB Output is correct
8 Correct 127 ms 784720 KB Output is correct
9 Correct 128 ms 784724 KB Output is correct
10 Correct 125 ms 784612 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 784212 KB Output is correct
2 Correct 123 ms 784112 KB Output is correct
3 Correct 120 ms 784188 KB Output is correct
4 Correct 120 ms 784208 KB Output is correct
5 Correct 121 ms 784228 KB Output is correct
6 Correct 127 ms 784464 KB Output is correct
7 Correct 125 ms 784724 KB Output is correct
8 Correct 126 ms 784912 KB Output is correct
9 Correct 123 ms 784836 KB Output is correct
10 Correct 126 ms 784788 KB Output is correct
11 Correct 125 ms 784724 KB Output is correct
12 Correct 129 ms 784816 KB Output is correct
13 Correct 127 ms 784720 KB Output is correct
14 Correct 128 ms 784724 KB Output is correct
15 Correct 125 ms 784612 KB Output is correct
16 Correct 139 ms 784812 KB Output is correct
17 Correct 184 ms 784704 KB Output is correct
18 Correct 143 ms 784928 KB Output is correct
19 Correct 166 ms 785004 KB Output is correct
20 Correct 130 ms 784724 KB Output is correct
21 Correct 216 ms 785004 KB Output is correct
22 Correct 194 ms 785316 KB Output is correct
23 Correct 321 ms 784724 KB Output is correct
24 Correct 191 ms 784860 KB Output is correct
25 Correct 231 ms 784980 KB Output is correct