Submission #1283224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283224		nemkho	Race (IOI11_race)	C++17	100 / 100	362 ms	81572 KiB

race

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pr pair <ll, int>
using namespace std;
const int N = 2e5 + 5;
map <ll, int> mp[N];
int n, k, h[N];
ll ans = 1e9, dist[N];
vector <pr> a[N];
void inp()
{
    cin >> n >> k;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        ll w;
        cin >> x >> y >> w;
        a[x].push_back({w, y});
        a[y].push_back({w, x});
    }
}
void dfs(int u, int pre)
{
    mp[u][dist[u]] = h[u];
    for (pr i : a[u])
    {
        int v = i.se;
        ll w = i.fi;
        if (v == pre)
            continue;
        h[v] = h[u] + 1;
        dist[v] = dist[u] + w;
        dfs(v, u);
        if (mp[u].size() < mp[v].size())
            swap(mp[u], mp[v]);
        for (auto i : mp[v])
        {
            ll tmp = k - i.fi + 2*dist[u];
            if (mp[u].count(tmp))
                ans = min(ans, 1LL*mp[u][tmp] + i.se - 2*h[u]);
        }
        for (auto i : mp[v])
        {
            if (mp[u].count(i.fi))
            {
                mp[u][i.fi] = min(mp[u][i.fi], i.se);
            }
            else
                mp[u][i.fi] = i.se;
        }
        map<ll,int>().swap(mp[v]);
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    n = N;
    k = K;
    for (int i = 0; i < n - 1; i++)
    {
        a[H[i][1]].push_back({L[i], H[i][0]});
        a[H[i][0]].push_back({L[i], H[i][1]});
    }
    mp[0][0] = 0;
    dfs(0, -1);
    return (ans == 1e9 ? -1 : ans);
}

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