Submission #888439

#	Time	Username	Problem	Language	Result	Execution time	Memory
888439		TitanSlayer	Race (IOI11_race)	C++14	100 / 100	393 ms	109652 KiB

race

#include "bits/stdc++.h"
#include "race.h"
using namespace std;
#define ll long long
#define ld long double
#define vv vector
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define mod 1000000007

typedef pair<ll, ll> pll;
typedef vv<ll> vll;
typedef vv<ld> vld;
typedef vv<pll> vpll;
typedef set<ll>::iterator sitr;

#define fastio                    \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);
///////////////////////////////////

ll n, k, ans = 1e9;
vector<map<ll, ll>> m(200005);
vv<vpll> v(200005);
pll offset[200005];

void dfs(ll node, ll par)
{
    // cout << node << " " << par << endl;
    m[node][0] = 0;
    offset[node] = {0, 0};
    for (auto child : v[node])
    {
        if (child.F == par)
            continue;
        dfs(child.F, node);

        offset[child.F].F += child.S;
        offset[child.F].S += 1;
        if (m[child.F].size() > m[node].size())
        {
            swap(m[child.F], m[node]);
            swap(offset[child.F], offset[node]);
        }

        for (auto itr_child : m[child.F])
        {
            ll dist = itr_child.F + offset[child.F].F;
            ll cnt = itr_child.S + offset[child.F].S;
            auto itr_par = m[node].find(k - dist - offset[node].F);
            if (itr_par != m[node].end())
                ans = min(ans, cnt + itr_par->second + offset[node].S);
        }

        for (auto itr_child : m[child.F])
        {
            ll dist = itr_child.F + offset[child.F].F - offset[node].F;
            ll cnt = itr_child.S + offset[child.F].S - offset[node].S;

            auto itr_par = m[node].find(dist);
            if (itr_par != m[node].end())
                m[node][dist] = min(cnt, m[node][dist]);
            else
                m[node][dist] = cnt;
        }
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    ll i, j, a, b, c;
    n = N;
    k = K;

    for (i = 0; i < n - 1; i++)
    {
        a = H[i][0];
        b = H[i][1];
        c = L[i];
        v[a].pb({b, c});
        v[b].pb({a, c});
    }

    dfs(0, -1);

    if (ans == 1e9)
        ans = -1;
    return (int)ans;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:73:11: warning: unused variable 'j' [-Wunused-variable]
   73 |     ll i, j, a, b, c;
      |           ^

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