oj.uz

Submission #468642

# Submission time Handle Problem Language Result Execution time Memory
468642 2021-08-29T07:23:52 Z idk321 Chase (CEOI17_chase) C++17
40 / 100
 1163 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 (ar.size() > 2) v.pop_back();
    }
};
SetLike dp[N][2][V];


void dfs(int node, int par) {

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

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

    for (int i = 0; i <= v; i++) {
        for (int j = 0; j < 2; j++) dp[node][j][i].insert({0, node});
    }
}

void transferRoot(int first, int second) {
    ll defaultValue = 0;
    for (int next : adj[second]) {
        if (next == first) continue;
        defaultValue += p[next];
    }


    for (int i = 0; i <= v; i++) {
        auto it0 = dp[first][0][i].begin();
        auto it1 = dp[first][1][i].begin();
        if ((*it0)[1] == second) it0++;
        if ((*it1)[1] == second) it1++;
        ll val0 = 0;
        ll val1 = 0;
        if (it0 != dp[first][0][i].end()) val0 = (*it0)[0];
        if (it1 != dp[first][1][i].end()) val1 = (*it1)[0];
        dp[second][0][i].insert({max(val0, val1 - p[second]), first});
        if (i != v) dp[second][1][i + 1].insert({max(val0 + defaultValue, val1 - p[second] + defaultValue), first});
    }


    for (int i = 1; i <= v; i++) {
        dp[second][1][i].add(0, p[first]);
        dp[second][1][i].add(1, p[first]);
    }
}

ll result = 0;

void dfsRoot(int node, int par) {
    for (int i = 0; i <= v; i++) {
        for (int j = 0; j < 2; j++) {
            result = max(result, (*dp[node][j][i].begin())[0]);
        }
    }
    //cout << node << " " << result << endl;

    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 276 ms 477252 KB Output is correct
2 Correct 311 ms 477044 KB Output is correct
3 Correct 270 ms 476972 KB Output is correct
4 Correct 277 ms 476984 KB Output is correct
5 Correct 278 ms 477036 KB Output is correct
6 Correct 278 ms 476992 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 477252 KB Output is correct
2 Correct 311 ms 477044 KB Output is correct
3 Correct 270 ms 476972 KB Output is correct
4 Correct 277 ms 476984 KB Output is correct
5 Correct 278 ms 477036 KB Output is correct
6 Correct 278 ms 476992 KB Output is correct
7 Correct 334 ms 491536 KB Output is correct
8 Correct 299 ms 478060 KB Output is correct
9 Correct 1163 ms 477988 KB Output is correct
10 Correct 350 ms 491588 KB Output is correct
11 Correct 299 ms 481520 KB Output is correct
12 Correct 321 ms 478532 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 392 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 276 ms 477252 KB Output is correct
2 Correct 311 ms 477044 KB Output is correct
3 Correct 270 ms 476972 KB Output is correct
4 Correct 277 ms 476984 KB Output is correct
5 Correct 278 ms 477036 KB Output is correct
6 Correct 278 ms 476992 KB Output is correct
7 Correct 334 ms 491536 KB Output is correct
8 Correct 299 ms 478060 KB Output is correct
9 Correct 1163 ms 477988 KB Output is correct
10 Correct 350 ms 491588 KB Output is correct
11 Correct 299 ms 481520 KB Output is correct
12 Correct 321 ms 478532 KB Output is correct
13 Runtime error 392 ms 524292 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -