oj.uz

Submission #46969

# Submission time Handle Problem Language Result Execution time Memory
46969 2018-04-25T15:23:44 Z nickyrio Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 184932 KB 
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define DEBUG(x) { cerr << #x << '=' << x << endl; }
#define Arr(a, l, r) { cerr << #a << " = {"; FOR(_, l, r) cerr << ' ' << a[_]; cerr << "}\n"; }
#define N 100100
#define pp pair<int, int>
#define endl '\n'
#define IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define taskname ""
#define bit(S, i) (((S) >> (i)) & 1)
void Max(long long &a, long long b) { a = a < b ? b : a; }
void Min(long long &a, long long b) { a = a < b ? a : b; }
using namespace std;

int n, k;
vector<int> e[N];
long long ans, a[N], DtoU[N][111], UtoD[N][111];

void dfs(int u, int p) {
    long long sum = 0;
    for (int v : e[u]) sum += a[v];
    DtoU[u][1] = UtoD[u][1] = sum;
    /*FOR(i, 1, k) {
        // Choose u
        if (i != 1 && p != -1) Max(UtoD[u][i], UtoD[p][]
    }*/
    for (int v : e[u]) if (v != p) {
        dfs(v, u);
        FOR(i, 1, k) {
            // Choose u
            if (i != 1) Max(DtoU[u][i], DtoU[v][i - 1] + sum - a[v]);
            // Don't choose u
            Max(DtoU[u][i], DtoU[v][i]);
        }
    }
}

int main() {
    #ifdef NERO
    freopen("test.inp","r",stdin);
    freopen("test.out","w",stdout);
    double stime = clock();
    #else 
        //freopen(taskname".inp","r",stdin);
        //freopen(taskname".out","w",stdout);
    #endif //NERO
    IO;
    cin >> n >> k;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 2, n) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    if (k == 0) {
        cout << 0;
        return 0;
    }
    ans = 0;
    FOR(root, 1, n) {
        FOR(i, 1, n) FOR(j, 1, k) DtoU[i][j] = 0;
        dfs(root, -1);
        FOR(i, 1, k) Max(ans, DtoU[root][i]);
    }
    cout << ans;
    #ifdef NERO
    double etime = clock();
    cerr << "\nExecution time: " << (etime - stime) / CLOCKS_PER_SEC * 1000 << " ms.\n";
    #endif // NERO
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2952 KB Output is correct
4 Correct 4 ms 2952 KB Output is correct
5 Correct 4 ms 2952 KB Output is correct
6 Correct 4 ms 2952 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2952 KB Output is correct
4 Correct 4 ms 2952 KB Output is correct
5 Correct 4 ms 2952 KB Output is correct
6 Correct 4 ms 2952 KB Output is correct
7 Correct 324 ms 4736 KB Output is correct
8 Correct 48 ms 4936 KB Output is correct
9 Correct 47 ms 4952 KB Output is correct
10 Correct 331 ms 4976 KB Output is correct
11 Correct 128 ms 5168 KB Output is correct
12 Correct 74 ms 5168 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4024 ms 184932 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2952 KB Output is correct
4 Correct 4 ms 2952 KB Output is correct
5 Correct 4 ms 2952 KB Output is correct
6 Correct 4 ms 2952 KB Output is correct
7 Correct 324 ms 4736 KB Output is correct
8 Correct 48 ms 4936 KB Output is correct
9 Correct 47 ms 4952 KB Output is correct
10 Correct 331 ms 4976 KB Output is correct
11 Correct 128 ms 5168 KB Output is correct
12 Correct 74 ms 5168 KB Output is correct
13 Execution timed out 4024 ms 184932 KB Time limit exceeded
14 Halted 0 ms 0 KB -