oj.uz

Submission #1092010

# Submission time Handle Problem Language Result Execution time Memory
1092010 2024-09-22T20:46:48 Z dpsaveslives Museum (CEOI17_museum) C++17
100 / 100
 624 ms 784468 KB 
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int INF = 1e9;
const int MAXN = 1e4;
vector<pair<int,int>> adj[MAXN+1];
int dp[MAXN+1][MAXN+1][2];
int st[MAXN+1];
void calcst(int u, int par){
    st[u] = 1;
    for(auto p : adj[u]){
        if(p.f == par) continue;
        calcst(p.f,u);
        st[u] += st[p.f];
    }
}
void dfs(int u,int par){
    //dp[u][0][0] = dp[u][0][1] = dp[u][1][0] = dp[u][1][1] = 0;
    for(int cur = 1; auto p : adj[u]){
        if(p.f == par) continue;
        dfs(p.f,u);
        cur += st[p.f];
        for(int i = cur;i>=2;--i){
            for(int j = max(0,i-cur+st[p.f]);j<=min(i,st[p.f]);++j){
                //cout << i-j << " " << j << " " << dp[u][i-j][0] << " " << dp[u][i-j][1] << " " << dp[p.f][j][0] << " " << dp[p.f][j][1] << "\n";
                dp[u][i][0] = min(dp[u][i][0],dp[p.f][j][0]+dp[u][i-j][1]+p.s);
                dp[u][i][0] = min(dp[u][i][0],dp[p.f][j][1]+dp[u][i-j][0]+2*p.s);
                dp[u][i][1] = min(dp[u][i][1],dp[p.f][j][1]+dp[u][i-j][1]+2*p.s);
                //cout << u << " " << i << " " << dp[u][i][0] << " " << dp[u][i][1] << "\n";
            }
        }

    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N,K,X; cin >> N >> K >> X;
    for(int i = 0;i<=N-2;++i){
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back({b,c}); adj[b].push_back({a,c});
    }
    for(int i = 1;i<=N;++i){
        for(int j = 2;j<=N;++j){
            dp[i][j][0] = dp[i][j][1] = INF;
        }
    }

    calcst(X,-1);
    dfs(X,-1);
    cout << dp[X][K][0] << "\n";
    return 0;
}

Compilation message

museum.cpp: In function 'void dfs(int, int)':
museum.cpp:21:22: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
   21 |     for(int cur = 1; auto p : adj[u]){
      |                      ^~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 783956 KB Output is correct
2 Correct 394 ms 783976 KB Output is correct
3 Correct 467 ms 784464 KB Output is correct
4 Correct 389 ms 784212 KB Output is correct
5 Correct 363 ms 783956 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 783956 KB Output is correct
2 Correct 394 ms 783976 KB Output is correct
3 Correct 467 ms 784464 KB Output is correct
4 Correct 389 ms 784212 KB Output is correct
5 Correct 363 ms 783956 KB Output is correct
6 Correct 361 ms 783956 KB Output is correct
7 Correct 407 ms 784468 KB Output is correct
8 Correct 624 ms 783952 KB Output is correct
9 Correct 540 ms 783896 KB Output is correct
10 Correct 401 ms 783956 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 372 ms 783956 KB Output is correct
7 Correct 394 ms 783976 KB Output is correct
8 Correct 467 ms 784464 KB Output is correct
9 Correct 389 ms 784212 KB Output is correct
10 Correct 363 ms 783956 KB Output is correct
11 Correct 361 ms 783956 KB Output is correct
12 Correct 407 ms 784468 KB Output is correct
13 Correct 624 ms 783952 KB Output is correct
14 Correct 540 ms 783896 KB Output is correct
15 Correct 401 ms 783956 KB Output is correct
16 Correct 370 ms 783956 KB Output is correct
17 Correct 396 ms 784012 KB Output is correct
18 Correct 422 ms 784212 KB Output is correct
19 Correct 559 ms 783920 KB Output is correct
20 Correct 386 ms 783952 KB Output is correct
21 Correct 437 ms 784208 KB Output is correct
22 Correct 388 ms 784052 KB Output is correct
23 Correct 552 ms 783888 KB Output is correct
24 Correct 426 ms 783956 KB Output is correct
25 Correct 460 ms 784464 KB Output is correct