Submission #661142

#	Time	Username	Problem	Language	Result	Execution time	Memory
661142		borisAngelov	Race (IOI11_race)	C++11	100 / 100	460 ms	103952 KiB

race

#include <iostream>
#include <utility>
#include <vector>
#include <tuple>
#include <map>
#include "race.h"

using namespace std;

const int maxn = 200005;
const int inf = 1000000000;

int H[maxn][2];
int L[maxn];

int n;
long long k;

vector<pair<int, int>> g[maxn];

long long pathToRoot[maxn];
int depth[maxn];

map<long long, int> info[maxn];

void dfs_precompute(int node, int parent, long long currPath, int currDepth) {
    pathToRoot[node] = currPath;
    depth[node] = currDepth;
    info[node][currPath] = currDepth;

    for (auto [v, w] : g[node]) {
        if (v == parent) continue;

        dfs_precompute(v, node, currPath + w, currDepth + 1);
    }
}

int ans = inf;

void dfs_small_to_large(int node, int parent) {
    long long target = k + 2 * pathToRoot[node];

    for (auto [v, w] : g[node]) {
        if (v == parent) continue;

        dfs_small_to_large(v, node);

        if (info[node].size() < info[v].size()) {
            swap(info[node], info[v]);
        }

        for (auto [dist, edges] : info[v]) {
            if (info[node].find(target - dist) != info[node].end()) {
                ans = min(ans, info[node][target - dist] + edges - 2 * depth[node]);
            }
        }

        for (auto [dist, edges] : info[v]) {
            if (info[node].find(dist) == info[node].end()) {
                info[node].insert({dist, edges});
            } else {
                info[node][dist] = min(info[node][dist], edges);
            }
        }
    }
}

int best_path(int A, int B, int edges[][2], int weights[]) {
    n = A;
    k = B;

    for (int i = 0; i < n - 1; ++i) {
        int u = edges[i][0];
        int v = edges[i][1];
        int w = weights[i];

        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    dfs_precompute(0, -1, 0, 0);
    dfs_small_to_large(0, -1);

    if (ans == inf) return -1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs_precompute(int, int, long long int, int)':
race.cpp:31:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     for (auto [v, w] : g[node]) {
      |               ^
race.cpp: In function 'void dfs_small_to_large(int, int)':
race.cpp:43:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |     for (auto [v, w] : g[node]) {
      |               ^
race.cpp:52:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |         for (auto [dist, edges] : info[v]) {
      |                   ^
race.cpp:58:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |         for (auto [dist, edges] : info[v]) {
      |                   ^

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