oj.uz

Submission #46983

# Submission time Handle Problem Language Result Execution time Memory
46983 2018-04-25T17:28:57 Z nickyrio Chase (CEOI17_chase) C++17
70 / 100
 958 ms 186332 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], sum[N];
 
void dfs(int u, int p) {
    DtoU[u][1] = sum[u];
    /*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) {
        FOR(i, 1, k) {
            // Choose v
            if (i != 1) Max(UtoD[v][i], UtoD[u][i - 1] + sum[v] - a[u]);
            else UtoD[v][i] = sum[v] - a[u];
            // Don't choose v
            Max(UtoD[v][i], UtoD[u][i]);
            Max(ans, UtoD[v][i]);
        }
        dfs(v, u);
        FOR(i, 1, k) {
            // Choose u
            if (i != 1) Max(DtoU[u][i], DtoU[v][i - 1] + sum[u] - 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;
    }
    FOR(u, 1, n) {
        for (int v : e[u]) sum[u] += a[v];
    }
    //Arr(sum, 1, n);
    ans = 0;
    if (n > 1000) {
        dfs(1, -1);
        UtoD[1][1] = sum[1];
        dfs(1, -1);
    }
    else {
        FOR(root, 1, n) {
            FOR(i, 1, n) FOR(j, 1, k) UtoD[i][j] = DtoU[i][j] = 0;
            UtoD[root][1] = sum[root];
            dfs(root, -1);
        }
    }
    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 3 ms 2680 KB Output is correct
2 Correct 3 ms 2788 KB Output is correct
3 Correct 3 ms 2788 KB Output is correct
4 Correct 4 ms 2788 KB Output is correct
5 Correct 4 ms 2788 KB Output is correct
6 Correct 3 ms 2788 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2680 KB Output is correct
2 Correct 3 ms 2788 KB Output is correct
3 Correct 3 ms 2788 KB Output is correct
4 Correct 4 ms 2788 KB Output is correct
5 Correct 4 ms 2788 KB Output is correct
6 Correct 3 ms 2788 KB Output is correct
7 Correct 816 ms 4704 KB Output is correct
8 Correct 109 ms 4704 KB Output is correct
9 Correct 92 ms 4796 KB Output is correct
10 Correct 958 ms 4796 KB Output is correct
11 Correct 316 ms 4808 KB Output is correct
12 Correct 155 ms 4808 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 186232 KB Output is correct
2 Correct 423 ms 186332 KB Output is correct
3 Correct 317 ms 186332 KB Output is correct
4 Correct 218 ms 186332 KB Output is correct
5 Correct 474 ms 186332 KB Output is correct
6 Correct 479 ms 186332 KB Output is correct
7 Correct 472 ms 186332 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2680 KB Output is correct
2 Correct 3 ms 2788 KB Output is correct
3 Correct 3 ms 2788 KB Output is correct
4 Correct 4 ms 2788 KB Output is correct
5 Correct 4 ms 2788 KB Output is correct
6 Correct 3 ms 2788 KB Output is correct
7 Correct 816 ms 4704 KB Output is correct
8 Correct 109 ms 4704 KB Output is correct
9 Correct 92 ms 4796 KB Output is correct
10 Correct 958 ms 4796 KB Output is correct
11 Correct 316 ms 4808 KB Output is correct
12 Correct 155 ms 4808 KB Output is correct
13 Correct 422 ms 186232 KB Output is correct
14 Correct 423 ms 186332 KB Output is correct
15 Correct 317 ms 186332 KB Output is correct
16 Correct 218 ms 186332 KB Output is correct
17 Correct 474 ms 186332 KB Output is correct
18 Correct 479 ms 186332 KB Output is correct
19 Correct 472 ms 186332 KB Output is correct
20 Incorrect 478 ms 186332 KB Output isn't correct
21 Halted 0 ms 0 KB -