oj.uz

Submission #1105122

# Submission time Handle Problem Language Result Execution time Memory
1105122 2024-10-25T13:27:49 Z AverageAmogusEnjoyer Museum (CEOI17_museum) C++17
100 / 100
 859 ms 784960 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());

int rng() {
    return abs((int)mrand());
}

// Current challenge: finish CSES problemset!!

const int nax = 10000 + 5, inf = 5e8;
int dp[nax][nax];
int dp2[nax][nax];
vector<pair<int,int>> adj[nax];
int n,k,start_node;
int sz[nax];

void dfs(int x,int p) {
    sz[x] = 1;
    for (int i=1;i<=n;i++)
        dp[x][i] = dp2[x][i] = inf;
    dp[x][1] = 0;
    dp2[x][1] = 0;
    for (auto &[y,c]: adj[x]) if (y != p) {
        dfs(y,x);
        for (int total = sz[x] + sz[y]; total >= 1; total--) {
            for (int other = min(sz[y],total); other >= 0 && total - other <= sz[x]; other--) {
                int me = total - other;
                cmin(dp[x][total],dp[x][me] + dp[y][other] + 2 * c);
                cmin(dp2[x][total],dp[x][me] + dp2[y][other] + c);
                cmin(dp2[x][total],dp2[x][me] + dp[y][other] + 2 * c);
            }
        }
        sz[x] += sz[y];
    }
}

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

    cin >> n >> k >> start_node;
    --start_node;
    for (int i=1,a,b,c;i<n;i++) {
        cin >> a >> b >> c;
        --a,--b;
        adj[a].emplace_back(b,c);
        adj[b].emplace_back(a,c);
    }
    dfs(start_node,-1);
    // for (int i=0;i<n;i++) {
    //     cout << "node " << i + 1 << endl;
    //     for (int j=1;j<=sz[i];j++)
    //         cout << "taking " << j << " nodes : " << dp[i][j] << endl;
    // }
    cout << dp2[start_node][k] << "\n";
}

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 784308 KB Output is correct
2 Correct 558 ms 784432 KB Output is correct
3 Correct 661 ms 784708 KB Output is correct
4 Correct 596 ms 784456 KB Output is correct
5 Correct 598 ms 784404 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 784308 KB Output is correct
2 Correct 558 ms 784432 KB Output is correct
3 Correct 661 ms 784708 KB Output is correct
4 Correct 596 ms 784456 KB Output is correct
5 Correct 598 ms 784404 KB Output is correct
6 Correct 623 ms 784200 KB Output is correct
7 Correct 742 ms 784584 KB Output is correct
8 Correct 859 ms 784388 KB Output is correct
9 Correct 768 ms 784384 KB Output is correct
10 Correct 650 ms 784584 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6736 KB Output is correct
2 Correct 1 ms 6736 KB Output is correct
3 Correct 2 ms 6736 KB Output is correct
4 Correct 1 ms 6736 KB Output is correct
5 Correct 2 ms 6736 KB Output is correct
6 Correct 602 ms 784308 KB Output is correct
7 Correct 558 ms 784432 KB Output is correct
8 Correct 661 ms 784708 KB Output is correct
9 Correct 596 ms 784456 KB Output is correct
10 Correct 598 ms 784404 KB Output is correct
11 Correct 623 ms 784200 KB Output is correct
12 Correct 742 ms 784584 KB Output is correct
13 Correct 859 ms 784388 KB Output is correct
14 Correct 768 ms 784384 KB Output is correct
15 Correct 650 ms 784584 KB Output is correct
16 Correct 642 ms 784200 KB Output is correct
17 Correct 620 ms 784456 KB Output is correct
18 Correct 703 ms 784572 KB Output is correct
19 Correct 792 ms 784216 KB Output is correct
20 Correct 566 ms 784240 KB Output is correct
21 Correct 609 ms 784456 KB Output is correct
22 Correct 574 ms 784356 KB Output is correct
23 Correct 704 ms 784456 KB Output is correct
24 Correct 613 ms 784456 KB Output is correct
25 Correct 801 ms 784960 KB Output is correct