답안 #37061 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
37061	2017-12-20T19:36:43 Z	DoanPhuDuc	Chase (CEOI17_chase)	C++	70 / 100	903 ms	445696 KB

chase

#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], C1[N][2], C2[N][2];
LL f[N][A][2], g[N][A][2], h[N][A];

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];
    g[u][0][0] = 0;
    g[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]);

            FOR(j, 0, 1)
                g[u][i][0] = max(g[u][i][0], g[v][i][j]);
            FOR(j, 0, 1)
                g[u][i][1] = max(g[u][i][1], g[v][i - 1][j] + S[u] - 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);
    }
   // FOR(i, 1, n) cout << a[i] << endl;
   //cout << endl;
    int Root = 1;
    FOR(u, 1, n)
        FOR(i, 0, m)
            FOR(k, 0, 1) f[u][i][k] = g[u][i][k] = -INFL;
    DFS(Root);
    DP(Root);
    FOR(u, 1, n) {
        FOR(i, 1, m)
            FOR(k, 0, 1) {
                if (f[u][i][k] < 0) f[u][i][k] = f[u][i - 1][k];
                if (g[u][i][k] < 0) g[u][i][k] = g[u][i - 1][k];
            }
    }
    FOR(u, 1, n)
        FOR(i, 1, m)
            FOR(k, 0, 1) h[u][i] = max(h[u][i], g[u][i][k]);
    LL ans = -INFL;
    FOR(w, 1, n) {
        FOR(i, 0, m) ans = max(ans, max(f[w][i][0], f[w][i][1] + a[p[w]]));
        FOR(i, 0, m) ans = max(ans, max(g[w][i][0], g[w][i][1] + a[p[w]]));
        FOR(i, 1, m)
            FOR(k, 0, 1) C1[i][k] = -INFL, C2[i][k] = -INFL;
        REP(k, 0, adj[w].size()) {
            int v = adj[w][k]; if (v == p[w]) continue;
            // u has drop
            FOR(i, 1, m - 1) {
                ans = max(ans, S[w] - a[w] + C1[i][1] + h[v][m - i - 1] + a[p[w]]);
                ans = max(ans, S[w] - a[w] + C1[i][0] + h[v][m - i - 1] + a[p[w]]);
            }
            // u has not drop
            FOR(i, 1, m) {
                ans = max(ans, C2[i][1] + h[v][m - i]);
                ans = max(ans, C2[i][0] + h[v][m - i]);
            }
            FOR(i, 1, m)
                FOR(j, 0, 1)
                    C1[i][j] = max(C1[i][j], f[v][i][j] + (j == 1 ? a[p[v]] : 0) - a[v]);
            FOR(i, 1, m)
                FOR(j, 0, 1)
                    C2[i][j] = max(C2[i][j], f[v][i][j] + (j == 1 ? a[p[v]] : 0));
        }
        reverse(adj[w].begin(), adj[w].end());
        FOR(i, 1, m)
            FOR(k, 0, 1) C1[i][k] = -INFL, C2[i][k] = -INFL;
        REP(k, 0, adj[w].size()) {
            int v = adj[w][k]; if (v == p[w]) continue;
            // u has drop
            FOR(i, 1, m - 1) {
                ans = max(ans, S[w] - a[w] + C1[i][1] + h[v][m - i - 1] + a[p[w]]);
                ans = max(ans, S[w] - a[w] + C1[i][0] + h[v][m - i - 1] + a[p[w]]);
            }
            // u has not drop
            FOR(i, 1, m) {
                ans = max(ans, C2[i][1] + h[v][m - i]);
                ans = max(ans, C2[i][0] + h[v][m - i]);
            }
            FOR(i, 1, m)
                FOR(j, 0, 1)
                    C1[i][j] = max(C1[i][j], f[v][i][j] + (j == 1 ? a[p[v]] : 0) - a[v]);
            FOR(i, 1, m)
                FOR(j, 0, 1)
                    C2[i][j] = max(C2[i][j], f[v][i][j] + (j == 1 ? a[p[v]] : 0));
        }
    }
    printf("%lld", 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:42:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^
chase.cpp: In function 'int main()':
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:96:9: note: in expansion of macro 'REP'
         REP(k, 0, adj[w].size()) {
         ^
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:118:9: note: in expansion of macro 'REP'
         REP(k, 0, adj[w].size()) {
         ^
chase.cpp:65: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:66: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:68: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

#	결과	메모리	Grader output
1	Correct	438780 KB	Output is correct
2	Correct	438780 KB	Output is correct
3	Correct	438780 KB	Output is correct
4	Correct	438780 KB	Output is correct
5	Correct	438780 KB	Output is correct
6	Correct	438780 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	438780 KB	Output is correct
2	Correct	0 ms	438780 KB	Output is correct
3	Correct	0 ms	438780 KB	Output is correct
4	Correct	0 ms	438780 KB	Output is correct
5	Correct	0 ms	438780 KB	Output is correct
6	Correct	0 ms	438780 KB	Output is correct
7	Correct	6 ms	438780 KB	Output is correct
8	Correct	3 ms	438780 KB	Output is correct
9	Correct	0 ms	438780 KB	Output is correct
10	Correct	9 ms	438780 KB	Output is correct
11	Correct	0 ms	438780 KB	Output is correct
12	Correct	3 ms	438780 KB	Output is correct

Subtask #3
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	736 ms	445696 KB	Output is correct
2	Correct	753 ms	445676 KB	Output is correct
3	Correct	633 ms	442496 KB	Output is correct
4	Correct	166 ms	442080 KB	Output is correct
5	Correct	873 ms	442080 KB	Output is correct
6	Correct	903 ms	442080 KB	Output is correct
7	Correct	833 ms	442080 KB	Output is correct

Subtask #4
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	438780 KB	Output is correct
2	Correct	0 ms	438780 KB	Output is correct
3	Correct	0 ms	438780 KB	Output is correct
4	Correct	0 ms	438780 KB	Output is correct
5	Correct	0 ms	438780 KB	Output is correct
6	Correct	0 ms	438780 KB	Output is correct
7	Correct	6 ms	438780 KB	Output is correct
8	Correct	3 ms	438780 KB	Output is correct
9	Correct	0 ms	438780 KB	Output is correct
10	Correct	9 ms	438780 KB	Output is correct
11	Correct	0 ms	438780 KB	Output is correct
12	Correct	3 ms	438780 KB	Output is correct
13	Correct	736 ms	445696 KB	Output is correct
14	Correct	753 ms	445676 KB	Output is correct
15	Correct	633 ms	442496 KB	Output is correct
16	Correct	166 ms	442080 KB	Output is correct
17	Correct	873 ms	442080 KB	Output is correct
18	Correct	903 ms	442080 KB	Output is correct
19	Correct	833 ms	442080 KB	Output is correct
20	Incorrect	879 ms	442080 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

답안 #37061

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 20.0 / 20.0

Subtask #3 30.0 / 30.0

Subtask #4 0 / 30.0

Subtask #1
20.0 / 20.0

Subtask #2
20.0 / 20.0

Subtask #3
30.0 / 30.0

Subtask #4
0 / 30.0