oj.uz

Submission #826529

# Submission time Handle Problem Language Result Execution time Memory
826529 2023-08-15T16:25:07 Z hafo Museum (CEOI17_museum) C++14
100 / 100
 644 ms 785120 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 = 1e9 + 69;
 
int n, u, v, w, sz[maxn], dp[maxn][maxn][2], f[2][maxn][2], k, node;
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 <= n; j++) 
            for(int en = 0; en < 2; en++) f[i][j][en] = oo;
    f[0][1][1] = 0;
    f[0][1][0] = 0;
    f[0][0][1] = 0;
    f[0][0][0] = 0;
    sz[u] = 1;
 
    for(int i = 1; i <= Size(g[u]); i++) {
        int v = g[u][i - 1].fi, w = g[u][i - 1].se;
        if(v == par) {
            for(int j = 0; j <= sz[u]; j++) 
                for(int en = 0; en < 2; en++) f[i & 1][j][en] = f[i & 1 ^ 1][j][en];
            continue;
        }
 
        for(int j = 0; j <= sz[u]; j++) {
            for(int pre = 0; pre <= sz[v]; pre++) {
                int cost = w;
                if(pre == 0) cost = 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 <= n; i++) 
        for(int en = 0; en < 2; en++) dp[u][i][en] = f[Size(g[u]) & 1][i][en];
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);
 
    cin>>n>>k>>node;
    for(int i = 1; i < n; i++) {
        cin>>u>>v>>w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
 
    dfs(node, 0);
    cout<<dp[node][k][0];
    return 0;
}

Compilation message

museum.cpp: In function 'void dfs(int, int)':
museum.cpp:45:69: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   45 |                 for(int en = 0; en < 2; en++) f[i & 1][j][en] = f[i & 1 ^ 1][j][en];
      |                                                                   ~~^~~
museum.cpp:53:48: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   53 |                 mini(f[i & 1][j + pre][0], f[i & 1 ^ 1][j][0] + dp[v][pre][1] + 2 * cost);
      |                                              ~~^~~
museum.cpp:54:48: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   54 |                 mini(f[i & 1][j + pre][0], f[i & 1 ^ 1][j][1] + dp[v][pre][0] + cost);
      |                                              ~~^~~
museum.cpp:55:48: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   55 |                 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 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 784548 KB Output is correct
2 Correct 553 ms 784628 KB Output is correct
3 Correct 556 ms 785120 KB Output is correct
4 Correct 574 ms 784656 KB Output is correct
5 Correct 564 ms 784588 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 784548 KB Output is correct
2 Correct 553 ms 784628 KB Output is correct
3 Correct 556 ms 785120 KB Output is correct
4 Correct 574 ms 784656 KB Output is correct
5 Correct 564 ms 784588 KB Output is correct
6 Correct 521 ms 784464 KB Output is correct
7 Correct 540 ms 784880 KB Output is correct
8 Correct 636 ms 784600 KB Output is correct
9 Correct 644 ms 784600 KB Output is correct
10 Correct 591 ms 784620 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 532 ms 784548 KB Output is correct
7 Correct 553 ms 784628 KB Output is correct
8 Correct 556 ms 785120 KB Output is correct
9 Correct 574 ms 784656 KB Output is correct
10 Correct 564 ms 784588 KB Output is correct
11 Correct 521 ms 784464 KB Output is correct
12 Correct 540 ms 784880 KB Output is correct
13 Correct 636 ms 784600 KB Output is correct
14 Correct 644 ms 784600 KB Output is correct
15 Correct 591 ms 784620 KB Output is correct
16 Correct 509 ms 784652 KB Output is correct
17 Correct 515 ms 784720 KB Output is correct
18 Correct 528 ms 784716 KB Output is correct
19 Correct 629 ms 784636 KB Output is correct
20 Correct 538 ms 784540 KB Output is correct
21 Correct 531 ms 784824 KB Output is correct
22 Correct 559 ms 784584 KB Output is correct
23 Correct 607 ms 784600 KB Output is correct
24 Correct 513 ms 784588 KB Output is correct
25 Correct 555 ms 785120 KB Output is correct