Submission #769290

#	Time	Username	Problem	Language	Result	Execution time	Memory
769290		jakobrs	Village (BOI20_village)	C++17	50 / 100	96 ms	28540 KiB

Village

#include <iostream>
#include <vector>

using i64 = int64_t;

const i64 INFINITY = __INT64_MAX__ / 1000;

std::pair<i64, i64> dfs(std::vector<std::vector<i64>> const &neighbours,
                        std::vector<std::pair<i64, i64>> &ann, i64 node,
                        i64 parent) {
    auto child_count = neighbours[node].size() - (parent != -1);
    if (child_count == 0) {
        return ann[node] = {INFINITY, 2};
    } else {
        std::vector<std::pair<i64, i64>> results;
        for (auto neighbour : neighbours[node]) {
            if (neighbour == parent) continue;
            results.push_back(dfs(neighbours, ann, neighbour, node));
        }

        // for k we have to move the root at least once
        i64 best_choice = -1;
        i64 why = INFINITY;
        for (i64 i = 0; i < child_count; i++) {
            if (results[i].second - results[i].first < why) {
                best_choice = i;
                why = results[i].second - results[i].first;
            }
        }

        i64 k = 0;
        for (i64 i = 0; i < child_count; i++) {
            if (i == best_choice) {
                k += results[i].second;
            } else {
                k += std::min(results[i].first, results[i].second);
            }
        }

        i64 l = 2;
        for (i64 i = 0; i < child_count; i++) {
            l += std::min(results[i].first, results[i].second);
        }

        return ann[node] = {k, l};
    }
}

std::pair<i64, i64> dfs_constructive(
    std::vector<std::vector<i64>> const &neighbours,
    std::vector<std::pair<i64, i64>> const &ann, i64 node, i64 parent, i64 mode,
    std::vector<i64> &assignment) {
    auto child_count = neighbours[node].size() - (parent != -1);
    if (child_count == 0) {
        if (mode & 0b01) {
            return {node, node};
        } else {
            std::cerr << "SOMETHING IS WRONG\n";
            return {-1, -1};
        }
    } else {
        std::vector<i64> children;
        for (auto neighbour : neighbours[node]) {
            if (neighbour == parent) continue;
            children.push_back(neighbour);
        }

        if (mode & 0b10 ||
            (mode == 0b11 && ann[node].first <= ann[node].second)) {
            // for k we have to move the root at least once
            i64 best_choice = -1;
            i64 why = INFINITY;
            for (i64 i = 0; i < child_count; i++) {
                if (ann[children[i]].second - ann[children[i]].first < why) {
                    best_choice = i;
                    why = ann[children[i]].second - ann[children[i]].first;
                }
            }

            i64 moving = node;

            for (i64 i = 0; i < child_count; i++) {
                auto [to, from] = dfs_constructive(
                    neighbours, ann, children[i], node,
                    i == best_choice ? 0b01 : 0b11, assignment);

                if (to != -1) {
                    assignment[moving] = to;
                    moving = from;
                }
            }

            assignment[moving] = node;  // ig

            return {-1, -1};
        } else {
            i64 moving = node;
            for (auto child : children) {
                auto [to, from] = dfs_constructive(neighbours, ann, child, node,
                                                   0b11, assignment);

                if (to != -1) {
                    assignment[moving] = to;
                    moving = from;
                }
            }

            return {node, moving};
        }
    }
}

int main() {
    i64 n;
    std::cin >> n;

    std::vector<std::vector<i64>> neighbours(n);
    for (i64 i = 0; i < n - 1; i++) {
        i64 a, b;
        std::cin >> a >> b;
        a--, b--;

        neighbours[a].push_back(b);
        neighbours[b].push_back(a);
    }

    std::vector<std::pair<i64, i64>> ann(n);

    auto [k, l] = dfs(neighbours, ann, 0, -1);

    std::cout << k << " 1\n";

    std::vector<i64> assignment(n);
    dfs_constructive(neighbours, ann, 0, -1, 0b10, assignment);

    for (i64 x : assignment) {
        std::cout << x + 1 << ' ';
    }
    std::cout << "\n";
    for (i64 x : assignment) {
        std::cout << x + 1 << ' ';
    }
}

Compilation message (stderr)

Village.cpp: In function 'std::pair<long int, long int> dfs(const std::vector<std::vector<long int> >&, std::vector<std::pair<long int, long int> >&, i64, i64)':
Village.cpp:24:27: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long int'} and 'long unsigned int' [-Wsign-compare]
   24 |         for (i64 i = 0; i < child_count; i++) {
      |                         ~~^~~~~~~~~~~~~
Village.cpp:32:27: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long int'} and 'long unsigned int' [-Wsign-compare]
   32 |         for (i64 i = 0; i < child_count; i++) {
      |                         ~~^~~~~~~~~~~~~
Village.cpp:41:27: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long int'} and 'long unsigned int' [-Wsign-compare]
   41 |         for (i64 i = 0; i < child_count; i++) {
      |                         ~~^~~~~~~~~~~~~
Village.cpp: In function 'std::pair<long int, long int> dfs_constructive(const std::vector<std::vector<long int> >&, const std::vector<std::pair<long int, long int> >&, i64, i64, i64, std::vector<long int>&)':
Village.cpp:73:31: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long int'} and 'long unsigned int' [-Wsign-compare]
   73 |             for (i64 i = 0; i < child_count; i++) {
      |                             ~~^~~~~~~~~~~~~
Village.cpp:82:31: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long int'} and 'long unsigned int' [-Wsign-compare]
   82 |             for (i64 i = 0; i < child_count; i++) {
      |                             ~~^~~~~~~~~~~~~

• Subtask 1: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50