oj.uz

Submission #77710

# Submission time Handle Problem Language Result Execution time Memory
77710 2018-09-30T02:55:19 Z ccinv Dostavljač (COCI18_dostavljac) C++14
140 / 140
 239 ms 4916 KB 
#include <bits/stdc++.h>
using namespace std;

#define oo 0x3f3f3f3f
#define mp make_pair
#define fi first
#define se second
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d) for(long _ = 0; (_ == 0 ? (_=clock()) != 0 : false); debug("%s time : %.4fs", d, (double)(clock() - _) / CLOCKS_PER_SEC))
#define FO(i,a,b) for (int i=(a);i<=(b);++i)
#define FD(i,a,b) for (int i=(a);i>=(b);--i)
#define FE(i,G,x) for(int i=(G).h[x];~i;i=(G).v[i].nxt)
typedef long long LL;
typedef pair<int, int> PII;

template <class T> inline bool chkmin(T& x, T y) { return x > y ? x = y, true : false; }
template <class T> inline bool chkmax(T& x, T y) { return x < y ? x = y, true : false; }

inline LL read(void) {
    LL x, f = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    return x * f;
}

#define N 505
template<typename T, size_t n, size_t m>
struct Graph {
    struct { int to, nxt; T w; } v[m];
    int h[n], cnt;
    Graph() { memset(h, -1, sizeof(h)); }
    void clear() { cnt = 0; memset(h, -1, sizeof(h)); }
    void add(int x, int y, const T& w = 0) { v[cnt] = {y, h[x], w}; h[x] = cnt++; }
};
Graph<bool, N, 2 * N> G;

LL f[N][N], g[N][N];
int n, t, x, y, T, a[N];

void solve(int x, int fa) {
    FE(i, G, x) { int to = G.v[i].to; if (to != fa) solve(to, x); }
    FE(i, G, x) {
        int v = G.v[i].to;
        if (v == fa) continue;
        FD(j, T, 3)FO(z, 1, j - 2) chkmax(g[x][j], g[x][j - z - 2] + f[v][z]);
        FD(j, T, 2)FO(z, 1, j - 1) chkmax(g[x][j], f[x][j - z - 1] + g[v][z]);
        FD(j, T, 3)FO(z, 1, j - 2) chkmax(f[x][j], f[x][j - z - 2] + f[v][z]);
    }
    FD(i, T, 1) chkmax(f[x][i], f[x][i - 1] + a[x]), chkmax(g[x][i], g[x][i - 1] + a[x]);
}

int main(void) {
    n = read(); T = read();
    FO(i, 1, n) a[i] = read();
    FO(i, 1, n - 1) { x = read(); y = read(); G.add(x, y); G.add(y, x); }
    solve(1, 0); cout << g[1][T] << endl;
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 720 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 896 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1136 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1464 KB Output is correct
2 Correct 5 ms 1484 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1872 KB Output is correct
2 Correct 31 ms 1872 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2320 KB Output is correct
2 Correct 20 ms 2332 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3104 KB Output is correct
2 Correct 115 ms 3112 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 4044 KB Output is correct
2 Correct 53 ms 4112 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 4904 KB Output is correct
2 Correct 27 ms 4916 KB Output is correct