oj.uz

Submission #469081

# Submission time Handle Problem Language Result Execution time Memory
469081 2021-08-30T16:07:33 Z Josia Chase (CEOI17_chase) C++14
70 / 100
 1098 ms 17820 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")


#include <bits/stdc++.h>

#define int int64_t

using namespace std;


vector<int> nearbyPigeons;
vector<int> pigeons;
vector<vector<int>> graph;
int crumbs;


void findNearPigeons(int v, int p) {
    if (p!=-1) nearbyPigeons[v] += pigeons[p];

    for (int i: graph[v]) {
        if (i==p) continue;
        nearbyPigeons[v] += pigeons[i];
        findNearPigeons(i, v);
    }
}




vector<int> options;        // all paths


map<int, int> localOptions; // one path for selecting crumbs


void findBestOptions(int v, int p) {
    int addToLocalOptions;
    if (p==-1) addToLocalOptions = nearbyPigeons[v];
    else addToLocalOptions = nearbyPigeons[v]-pigeons[p];

    for (int i: graph[v]) {
        if (i==p) continue;

        localOptions[addToLocalOptions]++;

        findBestOptions(i, v);

        localOptions[addToLocalOptions]--;
        if (localOptions[addToLocalOptions] == 0) localOptions.erase(addToLocalOptions);
    }


    localOptions[addToLocalOptions]++;

    int addToOptions = 0;

    auto pos = localOptions.end();
    auto limit = localOptions.begin();
    pos--;
    int used = crumbs;
    while (used>0 && pos!=limit) {
        addToOptions+=(*pos).first*min((*pos).second, used);
        used -= min((*pos).second, used);
        pos--;
    }

    if (used) {
        addToOptions+=(*pos).first*min((*pos).second, used);
        used -= min((*pos).second, used);
    }

    assert(used >= 0);

    options.push_back(addToOptions);


    localOptions[addToLocalOptions]--;
    if (localOptions[addToLocalOptions] == 0) localOptions.erase(addToLocalOptions);
}




signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n; cin >> n >> crumbs;

    pigeons.assign(n, 0);
    nearbyPigeons.assign(n, 0);

    for (int i = 0; i<n; i++) cin >> pigeons[i];


    graph.assign(n, vector<int>(0));

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

    findNearPigeons(0, -1);

    // for (int i: nearbyPigeons) {
    //     cout << i << " ";
    // }
    // cout << "\n";



    int best = 0;
    if (n>1000) {
    for (int i = 0; i<1; i++) {
        options.clear();
        findBestOptions(i, -1);

        // for (int i: options) {
        //     cout << i << " ";
        // }
        // cout << "\n";


        best = max(best, *max_element(options.begin(), options.end()));
        
    }}
    else {
        for (int i = 0; i<n; i++) {
        options.clear();
        findBestOptions(i, -1);

        // for (int i: options) {
        //     cout << i << " ";
        // }
        // cout << "\n";


        best = max(best, *max_element(options.begin(), options.end()));
        
    }
    }

    cout << best << "\n";




    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 276 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 276 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1098 ms 468 KB Output is correct
8 Correct 513 ms 468 KB Output is correct
9 Correct 152 ms 332 KB Output is correct
10 Correct 341 ms 384 KB Output is correct
11 Correct 332 ms 452 KB Output is correct
12 Correct 328 ms 384 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 17744 KB Output is correct
2 Correct 279 ms 17820 KB Output is correct
3 Correct 56 ms 9660 KB Output is correct
4 Correct 103 ms 9100 KB Output is correct
5 Correct 129 ms 9028 KB Output is correct
6 Correct 133 ms 9216 KB Output is correct
7 Correct 116 ms 9120 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 276 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1098 ms 468 KB Output is correct
8 Correct 513 ms 468 KB Output is correct
9 Correct 152 ms 332 KB Output is correct
10 Correct 341 ms 384 KB Output is correct
11 Correct 332 ms 452 KB Output is correct
12 Correct 328 ms 384 KB Output is correct
13 Correct 292 ms 17744 KB Output is correct
14 Correct 279 ms 17820 KB Output is correct
15 Correct 56 ms 9660 KB Output is correct
16 Correct 103 ms 9100 KB Output is correct
17 Correct 129 ms 9028 KB Output is correct
18 Correct 133 ms 9216 KB Output is correct
19 Correct 116 ms 9120 KB Output is correct
20 Incorrect 113 ms 9916 KB Output isn't correct
21 Halted 0 ms 0 KB -