oj.uz

Submission #468644

# Submission time Handle Problem Language Result Execution time Memory
468644 2021-08-29T08:10:20 Z idk321 Chase (CEOI17_chase) C++17
40 / 100
 982 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 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 148 ms 239792 KB Output is correct
2 Correct 151 ms 239824 KB Output is correct
3 Correct 148 ms 239812 KB Output is correct
4 Correct 144 ms 239804 KB Output is correct
5 Correct 148 ms 239840 KB Output is correct
6 Correct 148 ms 239896 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 239792 KB Output is correct
2 Correct 151 ms 239824 KB Output is correct
3 Correct 148 ms 239812 KB Output is correct
4 Correct 144 ms 239804 KB Output is correct
5 Correct 148 ms 239840 KB Output is correct
6 Correct 148 ms 239896 KB Output is correct
7 Correct 197 ms 251972 KB Output is correct
8 Correct 146 ms 241476 KB Output is correct
9 Correct 671 ms 241280 KB Output is correct
10 Correct 191 ms 251940 KB Output is correct
11 Correct 161 ms 244076 KB Output is correct
12 Correct 151 ms 241736 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 982 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 148 ms 239792 KB Output is correct
2 Correct 151 ms 239824 KB Output is correct
3 Correct 148 ms 239812 KB Output is correct
4 Correct 144 ms 239804 KB Output is correct
5 Correct 148 ms 239840 KB Output is correct
6 Correct 148 ms 239896 KB Output is correct
7 Correct 197 ms 251972 KB Output is correct
8 Correct 146 ms 241476 KB Output is correct
9 Correct 671 ms 241280 KB Output is correct
10 Correct 191 ms 251940 KB Output is correct
11 Correct 161 ms 244076 KB Output is correct
12 Correct 151 ms 241736 KB Output is correct
13 Runtime error 982 ms 524292 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -