oj.uz

Submission #469037

# Submission time Handle Problem Language Result Execution time Memory
469037 2021-08-30T13:20:35 Z Josia Chase (CEOI17_chase) C++14
20 / 100
 4000 ms 14660 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> 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

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.0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Execution timed out 4043 ms 1428 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4067 ms 14660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Execution timed out 4043 ms 1428 KB Time limit exceeded
8 Halted 0 ms 0 KB -