Submission #252607

#	Time	Username	Problem	Language	Result	Execution time	Memory
252607		Kubin	Race (IOI11_race)	C++11	9 / 100	3091 ms	10332 KiB

race

#include <bits/stdc++.h>

using namespace std;

int best_path(int _n, int k, int ends[][2], int weight[])
{
    const size_t n = _n;

    vector<vector<pair<size_t, int>>> adj(n);
    for(size_t i = 0; i < n - 1; i++)
    {
        size_t u = ends[i][0], v = ends[i][1];
        adj[u].emplace_back(v, weight[i]);
        adj[v].emplace_back(u, weight[i]);
    }

    function<pair<size_t, int>(size_t, size_t, size_t)> dfs = [&](size_t u, size_t t, size_t lock) -> pair<size_t, int> {
        if(u == t)
            return {0, 0};
        for(auto [v, w] : adj[u])
          if(v != lock)
        {
            auto [d, ww] = dfs(v, t, u);
            if(d != SIZE_MAX)
                return make_pair(d + 1, ww + w);
        }
        return {SIZE_MAX, 0};
    };

    size_t result = SIZE_MAX;
    for(size_t u = 0; u < n; u++)
      for(size_t v = 0; v < u; v++)
    {
        auto [d, w] = dfs(u, v, SIZE_MAX);
        if(w == k)
            result = min(result, d);
    }
    return result;
}

Compilation message (stderr)

race.cpp: In lambda function:
race.cpp:20:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         for(auto [v, w] : adj[u])
                  ^
race.cpp:23:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
             auto [d, ww] = dfs(v, t, u);
                  ^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:34:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         auto [d, w] = dfs(u, v, SIZE_MAX);
              ^

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