oj.uz

Submission #985214

# Submission time Handle Problem Language Result Execution time Memory
985214 2024-05-17T12:54:04 Z Neco_arc Museum (CEOI17_museum) C++17
100 / 100
 475 ms 175996 KB 
#include <bits/stdc++.h>
//#include <bits/debug.hpp>

#define ll long long
#define all(x) x.begin(), x.end()
#define Neco "Museum"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#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 maxn (int) 1e4 + 1

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

int n, k, rt;
vector<pair<int, int>> edges[maxn];
vector<int> dp[maxn][2];

vector<int> cb(vector<int> &P, vector<int> &Q, int w) {
    vector<int> ans(P.size() + Q.size() - 1, 1e9);
    ans[0] = 0;

    fi(i, 1, P.size() - 1) fi(j, 0, Q.size() - 1) {
        ans[i + j] = min(ans[i + j], P[i] + Q[j] + (j > 0) * w);
    }
    return ans;
}

vector<int> Min(vector<int> &P, vector<int> &Q) {
    vector<int> ans(P.size());
    fi(i, 0, P.size() - 1) ans[i] = min(P[i], Q[i]);
    return ans;
}

void dfs(int u, int par) {

    for(auto [v, w] : edges[u]) if(v != par) {
        dfs(v, u);

        vector<int> tmp1 = cb(dp[u][0], dp[v][1], w);
        vector<int> tmp2 = cb(dp[u][1], dp[v][0], 2 * w);
        dp[u][1] = Min(tmp1, tmp2);
        dp[u][0] = cb(dp[u][0], dp[v][0], 2 * w);
    }

}

void solve()
{

    cin >> n >> k >> rt;
    fi(i, 1, n - 1) {
        int x, y, w; cin >> x >> y >> w;
        edges[x].push_back({y, w}), edges[y].push_back({x, w});
    }

    fi(i, 1, n) fi(t, 0, 1) dp[i][t] = {0, 0};
    dfs(rt, 0);

    cout << dp[rt][1][k];

}


int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(Neco".inp", "r")) {
        freopen(Neco".inp", "r", stdin);
        freopen(Neco".out", "w", stdout);
    }


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


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


    return 0;
}

Compilation message

museum.cpp: In function 'std::vector<int> cb(std::vector<int>&, std::vector<int>&, int)':
museum.cpp:12:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define fi(i, a, b) for(int i = a; i <= b; i++)
......
   29 |     fi(i, 1, P.size() - 1) fi(j, 0, Q.size() - 1) {
      |        ~~~~~~~~~~~~~~~~~~             
museum.cpp:29:5: note: in expansion of macro 'fi'
   29 |     fi(i, 1, P.size() - 1) fi(j, 0, Q.size() - 1) {
      |     ^~
museum.cpp:12:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define fi(i, a, b) for(int i = a; i <= b; i++)
......
   29 |     fi(i, 1, P.size() - 1) fi(j, 0, Q.size() - 1) {
      |                               ~~~~~~~~~~~~~~~~~~
museum.cpp:29:28: note: in expansion of macro 'fi'
   29 |     fi(i, 1, P.size() - 1) fi(j, 0, Q.size() - 1) {
      |                            ^~
museum.cpp: In function 'std::vector<int> Min(std::vector<int>&, std::vector<int>&)':
museum.cpp:12:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define fi(i, a, b) for(int i = a; i <= b; i++)
......
   37 |     fi(i, 0, P.size() - 1) ans[i] = min(P[i], Q[i]);
      |        ~~~~~~~~~~~~~~~~~~             
museum.cpp:37:5: note: in expansion of macro 'fi'
   37 |     fi(i, 0, P.size() - 1) ans[i] = min(P[i], Q[i]);
      |     ^~
museum.cpp: In function 'int main()':
museum.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 4180 KB Output is correct
2 Correct 170 ms 4908 KB Output is correct
3 Correct 286 ms 175996 KB Output is correct
4 Correct 202 ms 53584 KB Output is correct
5 Correct 184 ms 13904 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 4180 KB Output is correct
2 Correct 170 ms 4908 KB Output is correct
3 Correct 286 ms 175996 KB Output is correct
4 Correct 202 ms 53584 KB Output is correct
5 Correct 184 ms 13904 KB Output is correct
6 Correct 168 ms 3488 KB Output is correct
7 Correct 240 ms 98496 KB Output is correct
8 Correct 475 ms 2812 KB Output is correct
9 Correct 356 ms 2900 KB Output is correct
10 Correct 190 ms 3740 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 163 ms 4180 KB Output is correct
7 Correct 170 ms 4908 KB Output is correct
8 Correct 286 ms 175996 KB Output is correct
9 Correct 202 ms 53584 KB Output is correct
10 Correct 184 ms 13904 KB Output is correct
11 Correct 168 ms 3488 KB Output is correct
12 Correct 240 ms 98496 KB Output is correct
13 Correct 475 ms 2812 KB Output is correct
14 Correct 356 ms 2900 KB Output is correct
15 Correct 190 ms 3740 KB Output is correct
16 Correct 166 ms 4944 KB Output is correct
17 Correct 165 ms 4656 KB Output is correct
18 Correct 211 ms 63572 KB Output is correct
19 Correct 430 ms 2784 KB Output is correct
20 Correct 184 ms 3932 KB Output is correct
21 Correct 233 ms 94428 KB Output is correct
22 Correct 164 ms 4388 KB Output is correct
23 Correct 381 ms 2788 KB Output is correct
24 Correct 175 ms 3712 KB Output is correct
25 Correct 290 ms 172480 KB Output is correct