Submission #521091

#	Time	Username	Problem	Language	Result	Execution time	Memory
521091		Lam_lai_cuoc_doi	Race (IOI11_race)	C++17	0 / 100	7 ms	14416 KiB

race

#include <iostream>
#include <cstdio>
#include <map>
#include <functional>
#include <vector>
//#include "race.h"

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 2e5 + 5;
constexpr int Inf = 1e9 + 7;
ll d[N];
vector<pair<int, int>> adj[N];
map<ll, int> cnt[N];
int ranks[N];

int Get(map<ll, int> &cnt, ll x)
{
    auto j = cnt.find(x);
    return j == cnt.end() ? Inf + 5 : j->second;
}

void Update(map<ll, int> &cnt, ll x, int y)
{
    auto j = cnt.find(x);
    if (j == cnt.end())
        cnt[x] = y;
    else
        j->second = min(j->second, y);
}

int best_path(int n, int k, int h[][2], int l[])
{
    int ans(Inf);

    function<void(int, int)> dfs = [&](int v, int p)
    {
        cnt[v][d[v]] = ranks[v];

        for (auto i : adj[v])
            if (i.first != p)
            {
                d[i.first] = d[v] + i.second;
                ranks[i.first] = ranks[v] + 1;
                dfs(i.first, v);

                if (cnt[v].size() < cnt[i.first].size())
                    swap(cnt[i.first], cnt[v]);

                for (auto j : cnt[i.first])
                    if (j.first - d[v] <= k)
                        ans = min(ans, Get(cnt[v], k - (j.first - d[v]) + d[v]) + j.second - 2 * ranks[v]);

                for (auto j : cnt[i.first])
                    if (j.first - d[v] <= k)
                        Update(cnt[v], j.first, j.second);

                cnt[i.first].clear();
            }

        // cerr << v << ": " << ans << "\n";
    };

    for (int i = 0; i < n - 1; ++i)
    {
        adj[h[i][0] + 1].emplace_back(h[i][1] + 1, l[i]);
        adj[h[i][1] + 1].emplace_back(h[i][0] + 1, l[i]);
    }

    ranks[1] = 1;
    dfs(1, -1);

    return ans >= Inf ? -1 : ans;
}

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