oj.uz

Submission #1106363

# Submission time Handle Problem Language Result Execution time Memory
1106363 2024-10-30T04:54:29 Z whoknow Museum (CEOI17_museum) C++17
100 / 100
 591 ms 3400 KB 
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define MAXN 10005
#define ii pair<int,int>
#define bit(i,j) ((i>>j)&1)
#define sz(i) (int)i.size()
#define endl '\n'
using namespace std;
const int INF = 1e9;
int n, k, st;
vector<ii>g[MAXN];
namespace sub1
{
vector<int> dp[MAXN][2];
vector<int> combine(vector<int>x, vector<int>y, int w)
{
    vector<int>ans(sz(x) + sz(y) - 1, INF);
    for(int i = 1; i < sz(x); i++)
        for(int j = 0; j < sz(y); j++)
            if(i + j <= k)
                ans[i + j] = min(ans[i + j], x[i] + y[j] + w);
    return ans;
}
vector<int>mn(vector<int>x, vector<int>y)
{
    for(int i = 0; i < sz(x); i++)
        y[i] = min(x[i], y[i]);
    return y;
}
void dfs(int u, int p, int cost)
{
    dp[u][0] = {0, cost};
    dp[u][1] = {INF, cost};
    for(ii i : g[u])
    {
        int v = i.F, w = i.S;
        if(v == p)
            continue;
        dfs(v, u, w);
        dp[u][1] = mn(dp[u][1], combine(dp[u][1], dp[v][0], w));
        dp[u][1] = mn(dp[u][1], combine(dp[u][0], dp[v][1], 0));
        dp[u][0] = mn(dp[u][0], combine(dp[u][0], dp[v][0], w));
        vector<int>().swap(dp[v][0]);
        vector<int>().swap(dp[v][1]);
    }
}
void solve()
{
    dfs(st, 0, 0);
    cout << dp[st][1][k];
}
}
main()
{
    if(fopen("TEST.inp","r"))
    {
        freopen("TEST.inp","r",stdin);
        freopen("TEST.out","w",stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k >> st;
    for(int i = 1; i < n; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x].push_back({y, z});
        g[y].push_back({x, z});
    }
    sub1::solve();
}

Compilation message

museum.cpp:55:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   55 | main()
      | ^~~~
museum.cpp: In function 'int main()':
museum.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen("TEST.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
museum.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen("TEST.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1104 KB Output is correct
2 Correct 1 ms 1104 KB Output is correct
3 Correct 1 ms 1104 KB Output is correct
4 Correct 1 ms 932 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 166 ms 1864 KB Output is correct
2 Correct 164 ms 2020 KB Output is correct
3 Correct 239 ms 3340 KB Output is correct
4 Correct 181 ms 2376 KB Output is correct
5 Correct 174 ms 2124 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 1864 KB Output is correct
2 Correct 164 ms 2020 KB Output is correct
3 Correct 239 ms 3340 KB Output is correct
4 Correct 181 ms 2376 KB Output is correct
5 Correct 174 ms 2124 KB Output is correct
6 Correct 158 ms 2028 KB Output is correct
7 Correct 206 ms 2852 KB Output is correct
8 Correct 591 ms 2044 KB Output is correct
9 Correct 446 ms 2296 KB Output is correct
10 Correct 206 ms 2092 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1104 KB Output is correct
2 Correct 1 ms 1104 KB Output is correct
3 Correct 1 ms 1104 KB Output is correct
4 Correct 1 ms 932 KB Output is correct
5 Correct 1 ms 1104 KB Output is correct
6 Correct 166 ms 1864 KB Output is correct
7 Correct 164 ms 2020 KB Output is correct
8 Correct 239 ms 3340 KB Output is correct
9 Correct 181 ms 2376 KB Output is correct
10 Correct 174 ms 2124 KB Output is correct
11 Correct 158 ms 2028 KB Output is correct
12 Correct 206 ms 2852 KB Output is correct
13 Correct 591 ms 2044 KB Output is correct
14 Correct 446 ms 2296 KB Output is correct
15 Correct 206 ms 2092 KB Output is correct
16 Correct 166 ms 2076 KB Output is correct
17 Correct 163 ms 1992 KB Output is correct
18 Correct 186 ms 2556 KB Output is correct
19 Correct 471 ms 2064 KB Output is correct
20 Correct 173 ms 2096 KB Output is correct
21 Correct 221 ms 2812 KB Output is correct
22 Correct 155 ms 1992 KB Output is correct
23 Correct 448 ms 2020 KB Output is correct
24 Correct 177 ms 2064 KB Output is correct
25 Correct 227 ms 3400 KB Output is correct