Submission #418562

#	Time	Username	Problem	Language	Result	Execution time	Memory
418562		snasibov05	Race (IOI11_race)	C++14	21 / 100	3058 ms	8924 KiB

race

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

using namespace std;

#define oo 1000000000
#define pii pair<int, int>
#define pb push_back
#define f first
#define s second

int ans = oo;
vector<vector<pii>> ed;
vector<int> dp;
vector<pii> v;

void dfs(int cur, int pr, int l, int k, int d){
    if (d > k) return;
    v.pb({d, l});
    for (auto [x, w] : ed[cur]){
        if (x == pr) continue;
        dfs(x, cur, l+1, k, d + w);
    }
}

int best_path(int n, int k, int h[][2], int l[]){
    ed.resize(n);
    for (int i = 0; i < n - 1; ++i) {
        ed[h[i][0]].pb({h[i][1], l[i]});
        ed[h[i][1]].pb({h[i][0], l[i]});
    }

    for (int i = 0; i < n; ++i){
        dp.resize(k+1);
        dp.assign(k+1, oo);
        dp[0] = 0;
        for (auto [x, w] : ed[i]){
            v.clear();
            dfs(x, i, 1, k, w);
            for (auto [d, l] : v){
                ans = min(ans, dp[k - d] + l);
            }
            for (auto [d, l] : v){
                dp[d] = min(dp[d], l);
            }
        }
    }

    if (ans == oo) ans = -1;

    return ans;

}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int, int, int, int)':
race.cpp:20:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |     for (auto [x, w] : ed[cur]){
      |               ^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:37:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |         for (auto [x, w] : ed[i]){
      |                   ^
race.cpp:40:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |             for (auto [d, l] : v){
      |                       ^
race.cpp:43:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |             for (auto [d, l] : v){
      |                       ^

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