Submission #1185493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185493		aaa2312	Race (IOI11_race)	C++20	100 / 100	386 ms	104056 KiB

race

#include "race.h"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;
using ll = long long;


int best_path(int N, int K, int H[][2], int L[])
{
    ll n, k;
    n=N;
    k=K;
    vector<vector<pair<ll, ll>>> adj(n);
    for (int i = 0; i < n - 1; ++i) {
        ll u, v, l;
        u=H[i][0];
        v=H[i][1];
        l=L[i];
        adj[u].push_back({v, l});
        adj[v].push_back({u, l});
    }
    vector<ll> dist(n);
    vector<ll> depth(n);
    function<void(ll, ll)> dfs = [&](ll u, ll p) {
        for (auto i: adj[u]) {
            if (i.first != p) {
                depth[i.first] = depth[u] + 1;
                dist[i.first] = dist[u] + i.second;
                dfs(i.first, u);
            }
        }
    };
    dfs(0, -1);
    ll ans = LLONG_MAX;
    vector<map<ll, ll>> mp(n);
    function<void(ll, ll)> dfs2 = [&](ll u, ll p) {
        mp[u][dist[u]] = depth[u];
        for (auto &[v, d]: adj[u]) {
            if (v != p) {
                dfs2(v, u);
                if (mp[v].size() > mp[u].size()) {
                    swap(mp[u], mp[v]);
                }
                for (auto &[de, mi]: mp[v]) {
                    if (mp[u].find(dist[u] + k - (de - dist[u])) != mp[u].end()) {
                        ans = min(ans, mi + mp[u][dist[u] + k - (de - dist[u])] - 2*depth[u]);
                    }
                }
                for (auto &[de, mi]: mp[v]) {
                    if (mp[u].find(de) == mp[u].end()) {
                        mp[u][de] = mi;
                    } else {
                        mp[u][de] = min(mp[u][de], mi);
                    }
                }
            }
        }
    };
    dfs2(0, -1);
    if (ans == LLONG_MAX) {
        return -1;
    } else {
        return ans;
    }
}

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