Submission #553644

#	Time	Username	Problem	Language	Result	Execution time	Memory
553644		timreizin	Race (IOI11_race)	C++17	100 / 100	850 ms	65512 KiB

race

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

using namespace std;

using ll = long long;

struct CentroidDecomposition
{
    int n, k;
    vector<bool> used;
    vector<vector<pair<int, ll>>> adj;
    vector<int> sizes, del1, del2;
    array<int, 1000001> counter1{}, counter2{};
    int res = -1;

    int calc(int v, int p)
    {
        sizes[v] = 1;
        for (auto [u, w] : adj[v])  if (u != p && !used[u]) sizes[v] += calc(u, v);
        return sizes[v];
    }

    int findCentroid(int v, int p, int all)
    {
        for (auto [u, w] : adj[v]) if (u != p && !used[u] && sizes[u] > all / 2) return findCentroid(u, v, all);
        return v;
    }

    void dfs(int v, int p, int l, ll d)
    {
        if (d <= k)
        {
            counter2[d] = min(counter2[d], l);
            del1.push_back(d);
            del2.push_back(d);
        }
        for (auto [u, w] : adj[v]) if (u != p && !used[u]) dfs(u, v, l + 1, d + w);
    }

    int build(int v)
    {
        int all = calc(v, 0);
        int centroid = findCentroid(v, 0, all);
        //calc res
        int res = 1e9;
        counter1[0] = 0;
        del1.push_back(0);
        for (auto [u, w]: adj[centroid])
        {
            if (!used[u])
            {
                dfs(u, centroid, 1, w);
                for (int i : del2) if (k - i >= 0) res = min(res, counter2[i] + counter1[k - i]);
                for (int i : del2)
                {
                    counter1[i] = min(counter1[i], counter2[i]);
                    counter2[i] = 1e9;
                }
                del2.clear();
            }
        }
        for (int i : del1) counter1[i] = 1e9;
        del1.clear();
        used[centroid] = true;
        for (auto [u, w] : adj[centroid]) if (!used[u]) res = min(res, build(u));
        return res;
    }

    CentroidDecomposition(vector<vector<pair<int, ll>>> adj, int k) : adj(adj), k(k)
    {
        int n = (int)adj.size() - 1;
        used.resize(n + 1);
        sizes.resize(n + 1);
        counter1.fill(1e9);
        counter2.fill(1e9);
        res = build(0);
        if (res == 1e9) res = -1;
    }

    int operator()()
    {
        return res;
    }

};


int best_path(int n, int k, int H[][2], int L[])
{
    vector<vector<pair<int, ll>>> adj(n + 1);
    for (int i = 0; i + 1 < n; ++i)
    {
        adj[H[i][0]].emplace_back(H[i][1], L[i]);
        adj[H[i][1]].emplace_back(H[i][0], L[i]);
    }
    return CentroidDecomposition(adj, k)();
}

Compilation message (stderr)

race.cpp: In constructor 'CentroidDecomposition::CentroidDecomposition(std::vector<std::vector<std::pair<int, long long int> > >, int)':
race.cpp:13:35: warning: 'CentroidDecomposition::adj' will be initialized after [-Wreorder]
   13 |     vector<vector<pair<int, ll>>> adj;
      |                                   ^~~
race.cpp:11:12: warning:   'int CentroidDecomposition::k' [-Wreorder]
   11 |     int n, k;
      |            ^
race.cpp:71:5: warning:   when initialized here [-Wreorder]
   71 |     CentroidDecomposition(vector<vector<pair<int, ll>>> adj, int k) : adj(adj), k(k)
      |     ^~~~~~~~~~~~~~~~~~~~~

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