oj.uz

Submission #635129

# Submission time Handle Problem Language Result Execution time Memory
635129 2022-08-25T12:53:37 Z nguyentu Museum (CEOI17_museum) C++14
80 / 100
 419 ms 1048576 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
#define int long long
const int inf = 1e18 + 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];
        }
    }
}

signed 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 1 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 144 ms 101984 KB Output is correct
2 Correct 152 ms 102624 KB Output is correct
3 Correct 323 ms 362436 KB Output is correct
4 Correct 201 ms 181196 KB Output is correct
5 Correct 156 ms 117820 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 101984 KB Output is correct
2 Correct 152 ms 102624 KB Output is correct
3 Correct 323 ms 362436 KB Output is correct
4 Correct 201 ms 181196 KB Output is correct
5 Correct 156 ms 117820 KB Output is correct
6 Correct 148 ms 101052 KB Output is correct
7 Correct 252 ms 251088 KB Output is correct
8 Correct 271 ms 100024 KB Output is correct
9 Correct 225 ms 100196 KB Output is correct
10 Correct 154 ms 101336 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 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 144 ms 101984 KB Output is correct
7 Correct 152 ms 102624 KB Output is correct
8 Correct 323 ms 362436 KB Output is correct
9 Correct 201 ms 181196 KB Output is correct
10 Correct 156 ms 117820 KB Output is correct
11 Correct 148 ms 101052 KB Output is correct
12 Correct 252 ms 251088 KB Output is correct
13 Correct 271 ms 100024 KB Output is correct
14 Correct 225 ms 100196 KB Output is correct
15 Correct 154 ms 101336 KB Output is correct
16 Correct 200 ms 243036 KB Output is correct
17 Correct 419 ms 866452 KB Output is correct
18 Correct 255 ms 316960 KB Output is correct
19 Correct 283 ms 240936 KB Output is correct
20 Correct 198 ms 241724 KB Output is correct
21 Runtime error 373 ms 1048576 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -