oj.uz

Submission #1118278

# Submission time Handle Problem Language Result Execution time Memory
1118278 2024-11-25T07:41:20 Z smokieboi Museum (CEOI17_museum) C++17
100 / 100
 314 ms 785320 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define nl '\n'
#define fu(i,a,b) for(int i=a; i<=b; i++)
#define fd(i,a,b) for(int i=a; i>=b; i--)
#define BIT(i, n) (((n)>>(i))&(1))
#define pii pair<int, int>
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define SZ(V) (int)(V.size())
#define pb push_back
#define eb emplace_back
#define NAME "quan"

int t,n,m,k,q;

const int N = 1e4 + 5;
const int MOD = 1e9 + 7;
const int inf = 2e9 + 7;

void add(int &a, int b) {a+=b; if(a>=MOD) a-=MOD;}
void sub(int &a, int b) {a-=b; if(a<0) a+=MOD;}

// dp[u][k][0/1] : số bước ít nhất để đi được k đỉnh ở subtree u và có quay lại u hay không

int sz[N];
int dp[N][N][2];
vector<pii> adj[N];
int root;

void dfs(int u, int p){
    dp[u][1][0] = dp[u][1][1] = 0;
    sz[u] = 1;
    for(pii it: adj[u]){
        int v = it.ff;
        int w = it.ss;
        if(v == p) continue;
        dfs(v, u);
        fd(i,sz[u],1)
            fd(j,sz[v],1){
                dp[u][i + j][0] = min(dp[u][i + j][0], dp[u][i][1] + dp[v][j][0] + w);
                dp[u][i + j][0] = min(dp[u][i + j][0], dp[u][i][0] + dp[v][j][1] + 2*w);
                dp[u][i + j][1] = min(dp[u][i + j][1], dp[u][i][1] + dp[v][j][1] + 2*w);
            }
        sz[u] += sz[v];
    }
}

void nhap(){
    cin >> n >> k >> root;
    fu(i,1,n-1){
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].eb(v, w);
        adj[v].eb(u, w);
    }
    memset(dp, 0x3f, sizeof dp);
    dfs(root, 0);
    cout << dp[root][k][0] << nl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(NAME".inp", "r")){
       freopen(NAME".inp", "r", stdin);
       freopen(NAME".out", "w", stdout);
    }
    nhap();
}

Compilation message

museum.cpp: In function 'int main()':
museum.cpp:69:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |        freopen(NAME".inp", "r", stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:70:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |        freopen(NAME".out", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 784212 KB Output is correct
2 Correct 209 ms 784212 KB Output is correct
3 Correct 248 ms 784212 KB Output is correct
4 Correct 284 ms 784212 KB Output is correct
5 Correct 232 ms 784212 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 784800 KB Output is correct
2 Correct 307 ms 784724 KB Output is correct
3 Correct 237 ms 785252 KB Output is correct
4 Correct 224 ms 784980 KB Output is correct
5 Correct 239 ms 784712 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 784800 KB Output is correct
2 Correct 307 ms 784724 KB Output is correct
3 Correct 237 ms 785252 KB Output is correct
4 Correct 224 ms 784980 KB Output is correct
5 Correct 239 ms 784712 KB Output is correct
6 Correct 233 ms 784776 KB Output is correct
7 Correct 264 ms 784968 KB Output is correct
8 Correct 314 ms 784640 KB Output is correct
9 Correct 243 ms 784592 KB Output is correct
10 Correct 227 ms 784724 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 784212 KB Output is correct
2 Correct 209 ms 784212 KB Output is correct
3 Correct 248 ms 784212 KB Output is correct
4 Correct 284 ms 784212 KB Output is correct
5 Correct 232 ms 784212 KB Output is correct
6 Correct 300 ms 784800 KB Output is correct
7 Correct 307 ms 784724 KB Output is correct
8 Correct 237 ms 785252 KB Output is correct
9 Correct 224 ms 784980 KB Output is correct
10 Correct 239 ms 784712 KB Output is correct
11 Correct 233 ms 784776 KB Output is correct
12 Correct 264 ms 784968 KB Output is correct
13 Correct 314 ms 784640 KB Output is correct
14 Correct 243 ms 784592 KB Output is correct
15 Correct 227 ms 784724 KB Output is correct
16 Correct 229 ms 784784 KB Output is correct
17 Correct 188 ms 784636 KB Output is correct
18 Correct 232 ms 784980 KB Output is correct
19 Correct 272 ms 784724 KB Output is correct
20 Correct 203 ms 784724 KB Output is correct
21 Correct 240 ms 784980 KB Output is correct
22 Correct 207 ms 784732 KB Output is correct
23 Correct 223 ms 784848 KB Output is correct
24 Correct 192 ms 784760 KB Output is correct
25 Correct 221 ms 785320 KB Output is correct