oj.uz

Submission #37056

# Submission time Handle Problem Language Result Execution time Memory
37056 2017-12-20T18:06:39 Z DoanPhuDuc Chase (CEOI17_chase) C++
40 / 100
 4000 ms 185540 KB 
#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }

using namespace std;

typedef long long LL;
typedef pair <int, int> II;

const int N = 1e5 + 10;
const int A = 1e2 + 10;
const LL INFL = (LL)1e18;

int n, m;
int a[N], p[N];

LL S[N], C[N];
LL f[N][A][2];

vector <int> adj[N];

void DFS(int u, int par = -1) {
    S[u] = a[u];
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k]; if (v == par) continue;
        S[u] += a[v];
        p[v] = u;
        DFS(v, u);
    }
}

void DP(int u, int par = -1) {
    f[u][0][0] = 0;
    f[u][1][1] = S[u] - a[u];
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k]; if (v == par) continue;
        DP(v, u);
        FOR(i, 1, m) {
            f[u][i][0] = max(f[u][i][0], f[v][i][1] + a[u]);
            f[u][i][0] = max(f[u][i][0], f[v][i][0]);

            f[u][i][1] = max(f[u][i][1], f[v][i - 1][1] + S[u] - a[v]);
            f[u][i][1] = max(f[u][i][1], f[v][i - 1][0] + S[u] - a[v] - a[u]);
        }
    }
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // LOCAL
    scanf("%d%d", &n, &m);
    FOR(i, 1, n) scanf("%d", &a[i]);
    FOR(i, 1, n - 1) {
        int u, v; scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    LL ans = -INFL;
    FOR(Root, 1, n) {
        memset(S, 0, sizeof S);
        FOR(u, 1, n)
            FOR(i, 0, m)
                FOR(k, 0, 1) f[u][i][k] = -INFL;
        DFS(Root);
        DP(Root);
        FOR(i, 0, m) ans = max(ans, max(f[Root][i][0], f[Root][i][1]));
    }
    cout << ans;
    return 0;
}

Compilation message

chase.cpp: In function 'void DFS(int, int)':
chase.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
chase.cpp:29:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^
chase.cpp: In function 'void DP(int, int)':
chase.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
chase.cpp:40:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^
chase.cpp: In function 'int main()':
chase.cpp:58:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
                          ^
chase.cpp:59:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 1, n) scanf("%d", &a[i]);
                                    ^
chase.cpp:61:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v; scanf("%d%d", &u, &v);
                                        ^

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 178596 KB Output is correct
2 Correct 3 ms 178596 KB Output is correct
3 Correct 3 ms 178596 KB Output is correct
4 Correct 3 ms 178596 KB Output is correct
5 Correct 0 ms 178596 KB Output is correct
6 Correct 0 ms 178596 KB Output is correct
7 Correct 629 ms 178596 KB Output is correct
8 Correct 119 ms 178596 KB Output is correct
9 Correct 106 ms 178596 KB Output is correct
10 Correct 633 ms 178596 KB Output is correct
11 Correct 276 ms 178596 KB Output is correct
12 Correct 153 ms 178596 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4000 ms 185540 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 178596 KB Output is correct
2 Correct 3 ms 178596 KB Output is correct
3 Correct 3 ms 178596 KB Output is correct
4 Correct 3 ms 178596 KB Output is correct
5 Correct 0 ms 178596 KB Output is correct
6 Correct 0 ms 178596 KB Output is correct
7 Correct 629 ms 178596 KB Output is correct
8 Correct 119 ms 178596 KB Output is correct
9 Correct 106 ms 178596 KB Output is correct
10 Correct 633 ms 178596 KB Output is correct
11 Correct 276 ms 178596 KB Output is correct
12 Correct 153 ms 178596 KB Output is correct
13 Execution timed out 4000 ms 185540 KB Execution timed out
14 Halted 0 ms 0 KB -