oj.uz

Submission #1097584

# Submission time Handle Problem Language Result Execution time Memory
1097584 2024-10-07T15:18:22 Z vjudge1 Museum (CEOI17_museum) C++17
100 / 100
 553 ms 746576 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

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

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e4 + 7;
const ll oo = (ll) 1e9 + 69;

int n, k, x, u, v, w, sz[maxn], dp[maxn][maxn][2], f[2][maxn][2];
vector<pa> g[maxn];

void dfs(int u, int par) {
    for(auto e:g[u]) {
        int v = e.fi;
        if(v == par) continue;
        dfs(v, u);
    }

    for(int i = 0; i < 2; i++) {
        for(int j = 0; j <= k; j++) {
            for(int t = 0; t < 2; t++) {
                f[i][j][t] = oo;
            }
        }
    }
    f[0][1][1] = 0;
    //f[0][1][0] = 0;
    // f[0][0][0] = 0;
    // f[0][0][1] = 0;
    sz[u] = 1;

    for(int i = 1; i <= Size(g[u]); i++) {
        int v = g[u][i - 1].fi;
        int w = g[u][i - 1].se;
        if(v == par) {
            for(int j = 0; j <= sz[u]; j++) {
                for(int t = 0; t < 2; t++) {
                    f[i & 1][j][t] = f[i & 1 ^ 1][j][t];
                }
            }
            continue;
        }

        for(int j = 0; j <= sz[u]; j++) {
            for(int pre = 0; pre <= sz[v]; pre++) {
                int cost = w * (pre > 0);
                mini(f[i & 1][j + pre][0], f[i & 1 ^ 1][j][0] + dp[v][pre][1] + 2 * cost);
                mini(f[i & 1][j + pre][0], f[i & 1 ^ 1][j][1] + dp[v][pre][0] + cost);
                mini(f[i & 1][j + pre][1], f[i & 1 ^ 1][j][1] + dp[v][pre][1] + 2 * cost);
            }
        }
        sz[u] += sz[v];
    }

    for(int i = 0; i <= k; i++) {
        for(int t = 0; t < 2; t++) {
            dp[u][i][t] = f[Size(g[u]) & 1][i][t];
        }
    }
    dp[u][0][0] = dp[u][0][1] = 0;
    dp[u][1][0] = 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>k>>x;
    for(int i = 1; i < n; i++) {
        cin>>u>>v>>w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    dfs(x, 0);
    cout<<min(dp[x][k][0], dp[x][k][1]);
    return 0;
}

Compilation message

museum.cpp: In function 'void dfs(int, int)':
museum.cpp:51:42: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   51 |                     f[i & 1][j][t] = f[i & 1 ^ 1][j][t];
      |                                        ~~^~~
museum.cpp:60:48: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   60 |                 mini(f[i & 1][j + pre][0], f[i & 1 ^ 1][j][0] + dp[v][pre][1] + 2 * cost);
      |                                              ~~^~~
museum.cpp:61:48: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   61 |                 mini(f[i & 1][j + pre][0], f[i & 1 ^ 1][j][1] + dp[v][pre][0] + cost);
      |                                              ~~^~~
museum.cpp:62:48: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   62 |                 mini(f[i & 1][j + pre][1], f[i & 1 ^ 1][j][1] + dp[v][pre][1] + 2 * cost);
      |                                              ~~^~~

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 50488 KB Output is correct
2 Correct 109 ms 50564 KB Output is correct
3 Correct 171 ms 50992 KB Output is correct
4 Correct 127 ms 50512 KB Output is correct
5 Correct 152 ms 50512 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 50488 KB Output is correct
2 Correct 109 ms 50564 KB Output is correct
3 Correct 171 ms 50992 KB Output is correct
4 Correct 127 ms 50512 KB Output is correct
5 Correct 152 ms 50512 KB Output is correct
6 Correct 108 ms 50376 KB Output is correct
7 Correct 148 ms 50772 KB Output is correct
8 Correct 243 ms 50512 KB Output is correct
9 Correct 205 ms 50536 KB Output is correct
10 Correct 139 ms 50392 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 107 ms 50488 KB Output is correct
7 Correct 109 ms 50564 KB Output is correct
8 Correct 171 ms 50992 KB Output is correct
9 Correct 127 ms 50512 KB Output is correct
10 Correct 152 ms 50512 KB Output is correct
11 Correct 108 ms 50376 KB Output is correct
12 Correct 148 ms 50772 KB Output is correct
13 Correct 243 ms 50512 KB Output is correct
14 Correct 205 ms 50536 KB Output is correct
15 Correct 139 ms 50392 KB Output is correct
16 Correct 154 ms 120916 KB Output is correct
17 Correct 313 ms 433408 KB Output is correct
18 Correct 183 ms 120912 KB Output is correct
19 Correct 243 ms 120652 KB Output is correct
20 Correct 168 ms 120868 KB Output is correct
21 Correct 504 ms 746160 KB Output is correct
22 Correct 469 ms 745808 KB Output is correct
23 Correct 553 ms 746068 KB Output is correct
24 Correct 471 ms 746096 KB Output is correct
25 Correct 522 ms 746576 KB Output is correct