Submission #469037

#	Time	Username	Problem	Language	Result	Execution time	Memory
469037		Josia	Chase (CEOI17_chase)	C++14	20 / 100	4067 ms	14660 KiB

chase

#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> pigeons;
vector<vector<int>> graph;
int crumbs;


vector<int> path;
vector<int> options;


void DFS(int v, int p) {
    path.push_back(v);

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


    for (int i = 0; i<(1<<path.size()); i++) {
        int res = 0;
        int minusres = 0;



        vector<int> simulatedPigeons = pigeons;
        int count = 0;
        for (int j = 0; j<path.size(); j++) {
            minusres += simulatedPigeons[path[j]];

            if (1<<j & i) {
                count ++;

                for (int k: graph[path[j]]) {
                    simulatedPigeons[path[j]] += simulatedPigeons[k];
                    simulatedPigeons[k] = 0;
                }
            }
        }
        if (count > crumbs) {
            continue;
        }


        for (int j = 0; j<path.size(); j++) {
            res += simulatedPigeons[path[j]];
        }


        options.push_back(res-minusres);
    }




    path.pop_back();
}



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

    int n; cin >> n >> crumbs;

    pigeons.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";



    for (int i = 0; i<n; i++) {
        DFS(i, -1);
    }



    cout << *max_element(options.begin(), options.end()) << "\n";




    return 0;
}

Compilation message (stderr)

chase.cpp: In function 'void DFS(int64_t, int64_t)':
chase.cpp:39:26: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for (int j = 0; j<path.size(); j++) {
      |                         ~^~~~~~~~~~~~
chase.cpp:56:26: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int j = 0; j<path.size(); j++) {
      |                         ~^~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30