oj.uz

답안 #1111352

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1111352 2024-11-12T07:26:52 Z Zero_OP Chase (CEOI17_chase) C++14
40 / 100
 4000 ms 177284 KB 
#include <bits/stdc++.h>

using namespace std;

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            return a = b, true;
        } return false;
    }

const int MAX_N = 1e5 + 5;
const int MAX_K = 100 + 5;

int N, K, p[MAX_N];
long long sum_neighbor[MAX_N];
vector<int> adj[MAX_N];
long long f[MAX_N][MAX_K], g[MAX_N][MAX_K], ans;

//f[u][i] = if p[u] > 0
//g[u][i] = if p[u] = 0

void dfs(int u, int pre){
    for(int v : adj[u]) if(v != pre){
        for(int i = 1; i <= K; ++i){
            f[v][i] = max(f[u][i - 1], g[u][i - 1]) - p[u] + sum_neighbor[v];
            g[v][i] = max(f[u][i], g[u][i]);
        }

        dfs(v, u);
    }

    maximize(ans, max(f[u][K], g[u][K]));
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    cin >> N >> K;
    for(int i = 0; i < N; ++i) cin >> p[i];
    for(int i = 0; i < N - 1; ++i){
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
        sum_neighbor[u] += p[v];
        sum_neighbor[v] += p[u];
    }

    if(K == 0){
        cout << 0 << '\n';
        return 0;
    }

    for(int i = 0; i < N; ++i){
        for(int u = 0; u < N; ++u) for(int k = 0; k < K; ++k) f[u][k] = g[u][k] = 0;
        for(int k = 1; k <= K; ++k) f[i][k] = sum_neighbor[i];
        dfs(i, -1);
    }
    cout << ans << '\n';

    return 0;
}

/*

12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12

10 2
1 9 1 9 9 1 9 1 1 1
1 2
2 3
3 4
3 5
2 6
1 7
7 8
8 9
7 10


*/

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4688 KB Output is correct
2 Correct 1 ms 4688 KB Output is correct
3 Correct 1 ms 4688 KB Output is correct
4 Correct 1 ms 4688 KB Output is correct
5 Correct 1 ms 2740 KB Output is correct
6 Correct 2 ms 4688 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4688 KB Output is correct
2 Correct 1 ms 4688 KB Output is correct
3 Correct 1 ms 4688 KB Output is correct
4 Correct 1 ms 4688 KB Output is correct
5 Correct 1 ms 2740 KB Output is correct
6 Correct 2 ms 4688 KB Output is correct
7 Correct 190 ms 9296 KB Output is correct
8 Correct 26 ms 9296 KB Output is correct
9 Correct 21 ms 9272 KB Output is correct
10 Correct 195 ms 9040 KB Output is correct
11 Correct 80 ms 9040 KB Output is correct
12 Correct 33 ms 9040 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4059 ms 177284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4688 KB Output is correct
2 Correct 1 ms 4688 KB Output is correct
3 Correct 1 ms 4688 KB Output is correct
4 Correct 1 ms 4688 KB Output is correct
5 Correct 1 ms 2740 KB Output is correct
6 Correct 2 ms 4688 KB Output is correct
7 Correct 190 ms 9296 KB Output is correct
8 Correct 26 ms 9296 KB Output is correct
9 Correct 21 ms 9272 KB Output is correct
10 Correct 195 ms 9040 KB Output is correct
11 Correct 80 ms 9040 KB Output is correct
12 Correct 33 ms 9040 KB Output is correct
13 Execution timed out 4059 ms 177284 KB Time limit exceeded
14 Halted 0 ms 0 KB -