oj.uz

답안 #146129

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
146129 2019-08-22T09:49:11 Z lyc Chase (CEOI17_chase) C++14
0 / 100
 88 ms 14780 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MAXN = 1e5;
const int MAXV = 105;

int N, V;
int P[MAXN];
vector<int> al[MAXN]; int pa[MAXN];
ll f[MAXN][MAXV], g[MAXN][MAXV], h[MAXN][MAXV][2];
ll surr[MAXN];

void down(int u, int p) {
    pa[u] = p;
    surr[u] = 0;
    for (auto v : al[u]) if (v != p) {
        down(v,u);
        surr[u] += P[v];
    }

    f[u][0] = 0;
    FOR(x,1,V) {
        for (auto v : al[u]) if (v != p) {
            f[u][x] = max({ f[u][x], f[v][x], f[v][x-1]+surr[u] });
        }
    }
    
}

void up(int u, int p) {
    FOR(x,1,V){
        h[u][x][0] = h[u][x][1] = 0;
        for (auto v : al[u]) if (v != p) {
            if (h[u][x][0] == 0 or f[v][x] > f[h[u][x][0]][x]) h[u][x][0] = v;
            else if (h[u][x][1] == 0 or f[v][x] > f[h[u][x][1]][x]) h[u][x][1] = v;
        }
    }

    for (auto v : al[u]) if (v != p) {
        g[v][0] = 0;
        FOR(x,1,V) {
            g[v][x] = max({
                        g[u][x],
                        (h[u][x][0] != v ? f[h[u][x][0]][x] : f[h[u][x][1]][x]),
                        g[u][x-1] + (surr[u] - P[v] + P[p]),
                        #define fp(y) f[y][x-1]-P[y]
                        (h[u][x-1][0] != v ? fp(h[u][x-1][0]) : fp(h[u][x-1][1])) + (surr[u] - P[v] + P[p]),
                    });
            //if (u == 2) cout << g[u][x] << " " << g[u][x-1] << " bbb " << v << " " << x << " :: " << g[v][x] << " zzzz " << g[u][x] << " " << (h[u][x][0] != v ? f[h[u][x][0]][x] : f[h[u][x][1]][x]) << " " << g[u][x-1] + (surr[u] - P[v] + P[p]) << " " << (h[u][x-1][0] != v ? fp(h[u][x-1][0]) : fp(h[u][x-1][1])) << endl;
            //if (u == 2) cout << h[u][x][0] << " " << h[u][x][1] << endl;
            //if (u == 7) cout << g[u][x] << " " << g[u][x-1] << " aaa " << v << " " << x << " :: " << g[v][x] << endl;
        }

        up(v,u);
    }

}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> V;
    FOR(i,1,N) { cin >> P[i]; }

    FOR(i,1,N-1) {
        int A, B; cin >> A >> B;
        al[A].push_back(B);
        al[B].push_back(A);
    }

    down(1,0);
    up(1,0);
    ll ans = 0;
    FOR(i,1,N){
        //cout << "i " << i << " :: " << f[i][V] << " " << g[i][V] << " " << g[i][V-1] << "+" << surr[i] << endl;
        ans = max({
                ans,
                f[i][V],
                g[i][V],
                g[i][V-1] + surr[i] + P[pa[i]]
                });
    }
    cout << ans << '\n';
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Incorrect 4 ms 2680 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Incorrect 4 ms 2680 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 88 ms 14780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Incorrect 4 ms 2680 KB Output isn't correct
5 Halted 0 ms 0 KB -