Submission #875461

#	Time	Username	Problem	Language	Result	Execution time	Memory
875461		AleXutzZu	Race (IOI11_race)	C++14	100 / 100	1060 ms	47272 KiB

race

#include "race.h"
#include <vector>
#include <map>

struct Graph {
private:
    std::vector<std::vector<std::pair<int, int>>> adj;
    int size;
    std::vector<int> subtree;
    std::vector<bool> removed;
    std::map<int, int> min_edges;
    int answer = -1;

    int calc_subtree(int node, int root = -1) {
        subtree[node] = 1;
        for (const auto &[x, weight]: adj[node]) {
            if (x == root || removed[x]) continue;
            subtree[node] += calc_subtree(x, node);
        }
        return subtree[node];
    }

    int find_centroid(int node, int tree_size, int root = -1) {
        for (const auto &[x, weight]: adj[node]) {
            if (x == root || removed[x]) continue;
            if (subtree[x] > tree_size / 2) return find_centroid(x, tree_size, node);
        }
        return node;
    }

    void search(int node, int root, bool assign, int sum, int target, int depth) {
        if (sum > target) return;
        if (assign) {
            if (min_edges[sum] == 0 || depth < min_edges[sum]) min_edges[sum] = depth;
        } else {
            if (sum == target) {
                if (answer == -1 || depth < answer) answer = depth;
            } else {
                if (min_edges[target - sum] != 0) {
                    if (answer == -1 || min_edges[target - sum] + depth < answer) {
                        answer = min_edges[target - sum] + depth;
                    }
                }
            }
        }

        for (const auto &[x, weight]: adj[node]) {
            if (x == root || removed[x]) continue;
            search(x, node, assign, sum + weight, target, depth + 1);
        }
    }


    void decompose(int node, int target) {
        int centroid = find_centroid(node, calc_subtree(node));
        removed[centroid] = true;


        for (const auto &[x, weight]: adj[centroid]) {
            if (removed[x]) continue;

            search(x, centroid, false, weight, target, 1);
            search(x, centroid, true, weight, target, 1);
        }

        min_edges.clear();

        for (const auto &[x, weight]: adj[centroid]) {
            if (removed[x]) continue;
            decompose(x, target);
        }

    }

public:
    explicit Graph(int size) : size(size) {
        adj.resize(size);
        subtree.resize(size, 0);
        removed.resize(size, false);
    }

    void add_edge(int x, int y, int c) {
        adj[x].emplace_back(y, c);
        adj[y].emplace_back(x, c);
    }

    int get_answer(int target) {
        decompose(0, target);
        return answer;
    }
};


int best_path(int N, int K, int H[][2], int L[]) {
    Graph tree(N);
    for (int i = 0; i < N - 1; ++i) {
        tree.add_edge(H[i][0], H[i][1], L[i]);
    }

    return tree.get_answer(K);
}

Compilation message (stderr)

race.cpp: In member function 'int Graph::calc_subtree(int, int)':
race.cpp:16:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |         for (const auto &[x, weight]: adj[node]) {
      |                          ^
race.cpp: In member function 'int Graph::find_centroid(int, int, int)':
race.cpp:24:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |         for (const auto &[x, weight]: adj[node]) {
      |                          ^
race.cpp: In member function 'void Graph::search(int, int, bool, int, int, int)':
race.cpp:47:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |         for (const auto &[x, weight]: adj[node]) {
      |                          ^
race.cpp: In member function 'void Graph::decompose(int, int)':
race.cpp:59:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |         for (const auto &[x, weight]: adj[centroid]) {
      |                          ^
race.cpp:68:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |         for (const auto &[x, weight]: adj[centroid]) {
      |                          ^

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57