oj.uz

Submission #468645

# Submission time Handle Problem Language Result Execution time Memory
468645 2021-08-29T08:11:20 Z idk321 Chase (CEOI17_chase) C++17
40 / 100
 897 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 begin() {
        return v.begin();
    }
    vector<array<ll, 2>>::iterator end() {
        return v.end();
    }
    void add(int ind, ll num) {
        if (ind < v.size()) {
            v[ind][0] += num;
        }
    }

    void insert(array<ll, 2> ar) {
        v.push_back(ar);
        sort(v.begin(), v.end(), comp_fn);
        if (v.size() > 2) v.pop_back();
    }
};
SetLike 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++) {
            dpSet[node][i].insert({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++) {
        dpSet[node][i].insert({0, node});
        dpSet[node][i].insert({0, node});
    }
}

void transferRoot(int first, int second) {

    for (int i = 0; i <= v; i++) {
        auto it0 = dpSet[first][i].begin();
        if ((*it0)[1] == second) it0++;
        ll val0 = 0;
        if (it0 != dpSet[first][i].end()) val0 = (*it0)[0];
        dpSet[second][i].insert({val0, first});
        dp[second][i] = max(dp[second][i], val0);
        if (i != v)  {
            dpSet[second][i + 1].insert({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
*/

Compilation message

chase.cpp: In member function 'void SetLike::add(int, ll)':
chase.cpp:32:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         if (ind < v.size()) {
      |             ~~~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 239904 KB Output is correct
2 Correct 142 ms 239852 KB Output is correct
3 Correct 140 ms 239852 KB Output is correct
4 Correct 144 ms 239812 KB Output is correct
5 Correct 145 ms 239936 KB Output is correct
6 Correct 145 ms 239812 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 239904 KB Output is correct
2 Correct 142 ms 239852 KB Output is correct
3 Correct 140 ms 239852 KB Output is correct
4 Correct 144 ms 239812 KB Output is correct
5 Correct 145 ms 239936 KB Output is correct
6 Correct 145 ms 239812 KB Output is correct
7 Correct 183 ms 248776 KB Output is correct
8 Correct 147 ms 241208 KB Output is correct
9 Correct 146 ms 241104 KB Output is correct
10 Correct 178 ms 248680 KB Output is correct
11 Correct 156 ms 243024 KB Output is correct
12 Correct 152 ms 241448 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 897 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 146 ms 239904 KB Output is correct
2 Correct 142 ms 239852 KB Output is correct
3 Correct 140 ms 239852 KB Output is correct
4 Correct 144 ms 239812 KB Output is correct
5 Correct 145 ms 239936 KB Output is correct
6 Correct 145 ms 239812 KB Output is correct
7 Correct 183 ms 248776 KB Output is correct
8 Correct 147 ms 241208 KB Output is correct
9 Correct 146 ms 241104 KB Output is correct
10 Correct 178 ms 248680 KB Output is correct
11 Correct 156 ms 243024 KB Output is correct
12 Correct 152 ms 241448 KB Output is correct
13 Runtime error 897 ms 524292 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -