oj.uz

Submission #1108747

# Submission time Handle Problem Language Result Execution time Memory
1108747 2024-11-05T00:31:19 Z Yang8on Museum (CEOI17_museum) C++17
100 / 100
 563 ms 323400 KB 
#include <bits/stdc++.h>
#define Y8o "Museum"
#define maxn (int) 1e4 + 5
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)
#define all(x) x.begin(), x.end()
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define fi(i, a, b) for(int i = a; i <= b; i ++)
#define fid(i, a, b) for(int i = a; i >= b; i --)

//#define f first
//#define s second

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r) (rng);
}
void iof() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);
    if(fopen(Y8o".inp", "r"))
    {
        freopen(Y8o".inp", "r", stdin);
//        freopen(Y8o".out", "w", stdout);
    }
}
void ctime() {
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

const ll INF = 1e18;

int n, k, st;
vector<pii> o[maxn];
int h[maxn];
vector<ll> dp[maxn][2];

vector<ll> cb(vector<ll> A, vector<ll> B, ll w) {
    vector<ll> ans (A.size() + B.size() - 1, INF);
    fi(i, 0, A.size() - 1) {
        fi(j, 0, B.size() - 1) {
            ans[i + j] = min(ans[i + j], A[i] + B[j] + (j > 0) * w);
        }
    }
    return ans;
}

vector<ll> minimum(vector<ll> A, vector<ll> B) {
    if(A.size() > B.size()) swap(A, B);
    while(A.size() < B.size()) A.push_back(INF);
    fi(i, 0, A.size() - 1) A[i] = min(A[i], B[i]);
    return A;
}

void dfs(int u, int p = 0) {
    dp[u][0] = { 0, 0 };
    dp[u][1] = { 0, -h[u] };

    for(auto [v, w] : o[u]) if(v != p) {
        h[v] = h[u] + w;
        dfs(v, u);
        vector<ll> tmp1 = cb(dp[u][0], dp[v][1], 2*w);
        vector<ll> tmp2 = cb(dp[u][1], dp[v][0], 2*w);

        dp[u][0] = cb(dp[u][0], dp[v][0], 2*w);
        dp[u][1] = minimum(tmp1, tmp2);
    }
}

void solve() {
    cin >> n >> k >> st;
    fi(i, 1, n - 1) {
        int u, v, w; cin >> u >> v >> w;
        o[u].push_back({ v, w }), o[v].push_back({ u, w });
    }

    dfs(st);
    cout << dp[st][1][k];
}


int main() {
    iof();

    int nTest = 1;
//    cin >> nTest;

    while(nTest --) {
        solve();
    }

    ctime();
    return 0;
}

Compilation message

museum.cpp: In function 'std::vector<long long int> cb(std::vector<long long int>, std::vector<long long int>, long long int)':
museum.cpp:10:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define fi(i, a, b) for(int i = a; i <= b; i ++)
......
   44 |     fi(i, 0, A.size() - 1) {
      |        ~~~~~~~~~~~~~~~~~~             
museum.cpp:44:5: note: in expansion of macro 'fi'
   44 |     fi(i, 0, A.size() - 1) {
      |     ^~
museum.cpp:10:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define fi(i, a, b) for(int i = a; i <= b; i ++)
......
   45 |         fi(j, 0, B.size() - 1) {
      |            ~~~~~~~~~~~~~~~~~~         
museum.cpp:45:9: note: in expansion of macro 'fi'
   45 |         fi(j, 0, B.size() - 1) {
      |         ^~
museum.cpp: In function 'std::vector<long long int> minimum(std::vector<long long int>, std::vector<long long int>)':
museum.cpp:10:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define fi(i, a, b) for(int i = a; i <= b; i ++)
......
   55 |     fi(i, 0, A.size() - 1) A[i] = min(A[i], B[i]);
      |        ~~~~~~~~~~~~~~~~~~             
museum.cpp:55:5: note: in expansion of macro 'fi'
   55 |     fi(i, 0, A.size() - 1) A[i] = min(A[i], B[i]);
      |     ^~
museum.cpp: In function 'void iof()':
museum.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen(Y8o".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 6984 KB Output is correct
2 Correct 145 ms 7756 KB Output is correct
3 Correct 480 ms 322376 KB Output is correct
4 Correct 250 ms 101448 KB Output is correct
5 Correct 166 ms 26704 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 6984 KB Output is correct
2 Correct 145 ms 7756 KB Output is correct
3 Correct 480 ms 322376 KB Output is correct
4 Correct 250 ms 101448 KB Output is correct
5 Correct 166 ms 26704 KB Output is correct
6 Correct 146 ms 5140 KB Output is correct
7 Correct 348 ms 197516 KB Output is correct
8 Correct 563 ms 3232 KB Output is correct
9 Correct 415 ms 3780 KB Output is correct
10 Correct 184 ms 5036 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1104 KB Output is correct
2 Correct 2 ms 1104 KB Output is correct
3 Correct 2 ms 1104 KB Output is correct
4 Correct 1 ms 1104 KB Output is correct
5 Correct 1 ms 1104 KB Output is correct
6 Correct 148 ms 6984 KB Output is correct
7 Correct 145 ms 7756 KB Output is correct
8 Correct 480 ms 322376 KB Output is correct
9 Correct 250 ms 101448 KB Output is correct
10 Correct 166 ms 26704 KB Output is correct
11 Correct 146 ms 5140 KB Output is correct
12 Correct 348 ms 197516 KB Output is correct
13 Correct 563 ms 3232 KB Output is correct
14 Correct 415 ms 3780 KB Output is correct
15 Correct 184 ms 5036 KB Output is correct
16 Correct 147 ms 9140 KB Output is correct
17 Correct 146 ms 7752 KB Output is correct
18 Correct 279 ms 121928 KB Output is correct
19 Correct 436 ms 3396 KB Output is correct
20 Correct 159 ms 5576 KB Output is correct
21 Correct 339 ms 179928 KB Output is correct
22 Correct 146 ms 7752 KB Output is correct
23 Correct 413 ms 4316 KB Output is correct
24 Correct 163 ms 4984 KB Output is correct
25 Correct 465 ms 323400 KB Output is correct