oj.uz

Submission #1106361

# Submission time Handle Problem Language Result Execution time Memory
1106361 2024-10-30T04:47:37 Z whoknow Museum (CEOI17_museum) C++17
100 / 100
 636 ms 401500 KB 
#include <bits/stdc++.h>
#define ll long long
#define int 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 = 1e18;
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));
    }
}
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:54:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   54 | main()
      | ^~~~
museum.cpp: In function 'int main()':
museum.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen("TEST.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
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.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 2 ms 1104 KB Output is correct
3 Correct 1 ms 1272 KB Output is correct
4 Correct 1 ms 1272 KB Output is correct
5 Correct 2 ms 1172 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 6496 KB Output is correct
2 Correct 143 ms 7724 KB Output is correct
3 Correct 516 ms 401500 KB Output is correct
4 Correct 235 ms 122124 KB Output is correct
5 Correct 146 ms 26628 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 6496 KB Output is correct
2 Correct 143 ms 7724 KB Output is correct
3 Correct 516 ms 401500 KB Output is correct
4 Correct 235 ms 122124 KB Output is correct
5 Correct 146 ms 26628 KB Output is correct
6 Correct 151 ms 5252 KB Output is correct
7 Correct 376 ms 226112 KB Output is correct
8 Correct 636 ms 3064 KB Output is correct
9 Correct 540 ms 4584 KB Output is correct
10 Correct 246 ms 5004 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 2 ms 1104 KB Output is correct
3 Correct 1 ms 1272 KB Output is correct
4 Correct 1 ms 1272 KB Output is correct
5 Correct 2 ms 1172 KB Output is correct
6 Correct 119 ms 6496 KB Output is correct
7 Correct 143 ms 7724 KB Output is correct
8 Correct 516 ms 401500 KB Output is correct
9 Correct 235 ms 122124 KB Output is correct
10 Correct 146 ms 26628 KB Output is correct
11 Correct 151 ms 5252 KB Output is correct
12 Correct 376 ms 226112 KB Output is correct
13 Correct 636 ms 3064 KB Output is correct
14 Correct 540 ms 4584 KB Output is correct
15 Correct 246 ms 5004 KB Output is correct
16 Correct 138 ms 8592 KB Output is correct
17 Correct 141 ms 8212 KB Output is correct
18 Correct 297 ms 149300 KB Output is correct
19 Correct 491 ms 3264 KB Output is correct
20 Correct 139 ms 5424 KB Output is correct
21 Correct 330 ms 212876 KB Output is correct
22 Correct 140 ms 7496 KB Output is correct
23 Correct 512 ms 3232 KB Output is correct
24 Correct 162 ms 5192 KB Output is correct
25 Correct 446 ms 382024 KB Output is correct