oj.uz

Submission #468646

# Submission time Handle Problem Language Result Execution time Memory
468646 2021-08-29T08:16:06 Z idk321 Chase (CEOI17_chase) C++17
40 / 100
 941 ms 524292 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100005;
const int V = 101;
int p[N];
int n, v;
vector<int> adj[N];


struct comp {
    bool operator () (const array<ll,2>& ar1, const array<ll,2>& ar2) const {
        return ar1 > ar2;
    }
};

bool comp_fn (const array<ll,2>& ar1, const array<ll,2>& ar2)  {
    return ar1 > ar2;
}


struct SetLike {
    vector<array<ll, 2>> v;

};


vector<array<ll, 2>>::iterator sbegin(vector<array<ll, 2>>& v) {
        return v.begin();
}

vector<array<ll, 2>>::iterator send(vector<array<ll, 2>>& v) {
    return v.end();
}


void sinsert(vector<array<ll, 2>>& v, array<ll, 2> ar) {
    v.push_back(ar);
    sort(v.begin(), v.end(), comp_fn);
    if (v.size() > 2) v.pop_back();
}

vector<array<ll, 2>> dpSet[N][V];
ll dp[N][V];

ll defaultValue[N];

void dfs(int node, int par) {
    ll val1 = 0;
    for (int next : adj[node]) {
        defaultValue[node] += p[next];
        if (next == par) {
            continue;
        }
        val1 += p[next];
        dfs(next, node);
    }

    dp[node][1] = max(dp[node][1], val1);
    for (int next : adj[node]) {
        if (next == par) continue;
        for (int i = 0; i <= v; i++) {
            sinsert(dpSet[node][i], {dp[next][i], next});
            if (i != v) dp[node][i + 1] = max(dp[node][i + 1], dp[next][i] + val1);
            dp[node][i] = max(dp[node][i], dp[next][i]);
        }
    }

    for (int i = 0; i <= v; i++) {
        sinsert(dpSet[node][i], {0, node});
        sinsert(dpSet[node][i], {0, node});
    }
}

void transferRoot(int first, int second) {

    for (int i = 0; i <= v; i++) {
        auto it0 = sbegin(dpSet[first][i]);
        if ((*it0)[1] == second) it0++;
        ll val0 = 0;
        if (it0 != send(dpSet[first][i])) val0 = (*it0)[0];
        sinsert(dpSet[second][i], {val0, first});
        dp[second][i] = max(dp[second][i], val0);
        if (i != v)  {
            sinsert(dpSet[second][i + 1], {val0 + defaultValue[first] - p[second], first});
            dp[second][i + 1] = max(dp[second][i + 1], val0 + defaultValue[first] - p[second]);
            dp[second][i + 1] = max(dp[second][i + 1], val0 + defaultValue[second]);
        }
        if (i + 2 <= v) {
            dp[second][i + 2] = max(dp[second][i + 2], val0 + defaultValue[first] - p[second] + defaultValue[second]);
        }
    }
    for (int next : adj[second]) {
        if (next == first) continue;
        for (int i = 0; i <= v; i++) {

            if (i != v) dp[second][i + 1] = max(dp[second][i + 1], dp[next][i] + defaultValue[second]);
            dp[second][i] = max(dp[second][i], dp[next][i]);
        }
    }
}

ll result = 0;

void dfsRoot(int node, int par) {
    for (int i = 0; i <= v; i++) {

        result = max(result, dp[node][i]);

    }


    for (int next : adj[node]) {
        if (next == par) continue;

        transferRoot(node, next);
        dfsRoot(next, node);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> v;
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    dfs(1, -1);

    dfsRoot(1, -1);
    cout << result << "\n";
}

/*
12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12
*/

/*
10 3
10 1 1 1 1 10 1 10 1 10
1 2
2 3
3 4
4 5
5 6
3 7
7 8
9 4
9 10
*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 239784 KB Output is correct
2 Correct 141 ms 239812 KB Output is correct
3 Correct 141 ms 239940 KB Output is correct
4 Correct 145 ms 239828 KB Output is correct
5 Correct 144 ms 239812 KB Output is correct
6 Correct 143 ms 239828 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 239784 KB Output is correct
2 Correct 141 ms 239812 KB Output is correct
3 Correct 141 ms 239940 KB Output is correct
4 Correct 145 ms 239828 KB Output is correct
5 Correct 144 ms 239812 KB Output is correct
6 Correct 143 ms 239828 KB Output is correct
7 Correct 193 ms 248772 KB Output is correct
8 Correct 150 ms 241196 KB Output is correct
9 Correct 149 ms 241100 KB Output is correct
10 Correct 183 ms 248712 KB Output is correct
11 Correct 158 ms 243228 KB Output is correct
12 Correct 148 ms 241504 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 941 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 239784 KB Output is correct
2 Correct 141 ms 239812 KB Output is correct
3 Correct 141 ms 239940 KB Output is correct
4 Correct 145 ms 239828 KB Output is correct
5 Correct 144 ms 239812 KB Output is correct
6 Correct 143 ms 239828 KB Output is correct
7 Correct 193 ms 248772 KB Output is correct
8 Correct 150 ms 241196 KB Output is correct
9 Correct 149 ms 241100 KB Output is correct
10 Correct 183 ms 248712 KB Output is correct
11 Correct 158 ms 243228 KB Output is correct
12 Correct 148 ms 241504 KB Output is correct
13 Runtime error 941 ms 524292 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -