oj.uz

Submission #635130

# Submission time Handle Problem Language Result Execution time Memory
635130 2022-08-25T12:54:47 Z nguyentu Museum (CEOI17_museum) C++14
100 / 100
 528 ms 785472 KB 
#include <bits/stdc++.h>

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

#define ii pair<int , int>  
#define iv pair<ii , ii>
#define iii pair<int , ii>
#define fi first
#define se second
const int inf = 1e9 + 7;
const int MAX_N = 1e4 + 7;
const int MOD = 1e9 + 7;

int f[2][MAX_N][MAX_N];
int num[MAX_N];
vector<ii> adj[MAX_N];
int n , k , x;

// Solution : Knapsack on tree
// f[status][u][num] là tổng chi phí đường đi ngắn nhất chọn được
// num thằng phân biệt (kể cả u) trong subtree u có root là x
// với status 0 là chưa đi hết
//     status 1 là đi hết cuối đường
// Nhận xét tham lam là cách đi ngắn nhất là đi qua các cạnh nối đỉnh 2 lần
// và chỉ 1 lần cho cuối đường
// Formula : + f[0][u][num + new_num] = max(f[0][u][num + new_num] , f[0][v][new_num] + f[0][u][num] + 2*c);
//           + f[0][u][num + new_num] = max(f[0][u][num + new_num] , f[1][v][new_num] + f[0][u][num] + 2*c)
//           + f[1][u][num + new_num] = max(f[1][u][num + new_num] , f[1][v][new_num] + f[1][u][num] + c); 

void DFS(int u , int father) {
    num[u] = 1;
    f[0][u][1] = f[1][u][1] = 0;
    for (auto edge : adj[u]) {
        int v , w;
        tie(v , w) = edge;
        if (v != father) {
            DFS(v , u);
            for (int i = num[u] ; i >= 0 ; i --) {
                for (int j = num[v] ; j >= 1 ; j--) {
                    f[0][u][i + j] = min(f[0][u][i + j] , f[0][u][i] + f[0][v][j] + 2*w);
                    f[1][u][i + j] = min(f[1][u][i + j] , f[1][u][i] + f[0][v][j] + 2*w);
                    f[1][u][i + j] = min(f[1][u][i + j] , f[0][u][i] + f[1][v][j] + w);
                }
            }
            num[u] += num[v];
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> k >> x;
    for (int i = 1 ; i < n ; i++) {
        int u , v , c; cin >> u >> v >> c;
        adj[u].push_back(ii(v , c)); 
        adj[v].push_back(ii(u , c));
    }
    for (int status = 0 ; status <= 1 ; status++) {
        for (int i = 1 ; i <= n ; i ++) {
            for (int j = 1 ; j <= k ; j++) {
                f[status][i][j] = inf;
            }
        }
    }
    DFS(x , -1);
    cout << f[1][x][k];
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 91240 KB Output is correct
2 Correct 119 ms 91576 KB Output is correct
3 Correct 233 ms 220784 KB Output is correct
4 Correct 156 ms 131004 KB Output is correct
5 Correct 127 ms 99056 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 91240 KB Output is correct
2 Correct 119 ms 91576 KB Output is correct
3 Correct 233 ms 220784 KB Output is correct
4 Correct 156 ms 131004 KB Output is correct
5 Correct 127 ms 99056 KB Output is correct
6 Correct 121 ms 90700 KB Output is correct
7 Correct 189 ms 165900 KB Output is correct
8 Correct 343 ms 90320 KB Output is correct
9 Correct 259 ms 90588 KB Output is correct
10 Correct 138 ms 90956 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 0 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 122 ms 91240 KB Output is correct
7 Correct 119 ms 91576 KB Output is correct
8 Correct 233 ms 220784 KB Output is correct
9 Correct 156 ms 131004 KB Output is correct
10 Correct 127 ms 99056 KB Output is correct
11 Correct 121 ms 90700 KB Output is correct
12 Correct 189 ms 165900 KB Output is correct
13 Correct 343 ms 90320 KB Output is correct
14 Correct 259 ms 90588 KB Output is correct
15 Correct 138 ms 90956 KB Output is correct
16 Correct 149 ms 161704 KB Output is correct
17 Correct 256 ms 473520 KB Output is correct
18 Correct 177 ms 198700 KB Output is correct
19 Correct 338 ms 160716 KB Output is correct
20 Correct 150 ms 161220 KB Output is correct
21 Correct 397 ms 785012 KB Output is correct
22 Correct 365 ms 784400 KB Output is correct
23 Correct 528 ms 784524 KB Output is correct
24 Correct 372 ms 784504 KB Output is correct
25 Correct 417 ms 785472 KB Output is correct