Submission #473736

#	Time	Username	Problem	Language	Result	Execution time	Memory
473736		Lam_lai_cuoc_doi	Race (IOI11_race)	C++17	100 / 100	508 ms	103792 KiB

race

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 2e5 + 5;
constexpr int Inf = 1e9 + 7;
int ans(Inf), k, ranks[N];
ll dep[N];
map<ll, int> dp[N];
vector<pair<int, int>> adj[N];

int Get(int x, ll v)
{
    auto j = dp[x].find(v);
    return j == dp[x].end() ? Inf : j->second;
}

void Update(int x, ll pos, int v)
{
    auto j = dp[x].find(pos);
    if (j == dp[x].end())
        dp[x][pos] = v;
    else
        j->second = min(j->second, v);
}

void dfs(int v, int p = -1)
{
    dp[v][dep[v]] = ranks[v];

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

            dfs(i.first, v);

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

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

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

int best_path(int n, int kk, int h[][2], int l[])
{
    for (int i = 0; i < n - 1; ++i)
    {
        adj[h[i][0]].emplace_back(h[i][1], l[i]);
        adj[h[i][1]].emplace_back(h[i][0], l[i]);
    }
    k = kk;
    ranks[0] = 1;
    dfs(0);

    return (ans >= n ? -1 : ans);
}

Compilation message (stderr)

race.cpp: In function 'void read(T&)':
race.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^

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