Submission #1163215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163215		DangKhoizzzz	Race (IOI11_race)	C++20	43 / 100	219 ms	79300 KiB

race

#include <bits/stdc++.h>
#define ll long long
#define pii pair <ll, ll>
#define fi first
#define se second

using namespace std;

const ll INF = 1e9;
const ll maxn = 1e6 + 7;

ll n , k , depth[maxn] , h[maxn] ;
ll ans = INF;
vector <pii> g[maxn];

void dfs_build(ll u , ll p)
{
    for(pii e: g[u])
    {
        ll v = e.fi , w = e.se;
        if(v == p) continue;
        depth[v] = depth[u] + w;
        h[v] = h[u] + 1;
        dfs_build(v , u);
    }
}

void merging(map <ll , ll> &a , map <ll , ll> &b , ll reqh , ll reqdepth)
{
    if(a.size() < b.size()) swap(a , b);

    for(pii tmp: b)
    {
        ll v1 = tmp.fi;
        ll v2 = tmp.se;

        if(a.count(k - v1 + 2*reqdepth))
        {
            ans = min(ans , a[k - v1 + 2*reqdepth] + v2 - 2*reqh);
        }

        if(a.count(v1)) a[v1] = min(a[v1] , v2);
        else a[v1] = v2; 
    }

    if(a.count(k + reqdepth)) 
    {
        ans = min(ans , a[k + reqdepth] - reqh);
    }
}

map <ll , ll> dfs(ll u , ll p)
{
    map <ll , ll> res;
    res[depth[u]] = h[u];

    for(pii tmp: g[u])
    {
        ll v = tmp.fi;
        if(v == p) continue;
        map <ll , ll> con = dfs(v , u);
        merging(res , con , h[u] , depth[u]);
    }
    return res;
}


int best_path(int N, int K, int H[][2], int L[])
{
    n = N;
    k = K;

    for(ll i = 0; i < n-1; i++)
    {
        ll u = H[i][0] , v = H[i][1] , w = L[i];
        u++ , v++;
        g[u].push_back({v , w});
        g[v].push_back({u , w});
    }
    dfs_build(1 , 1);
    dfs(1 , 1);

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

// void solve()
// {
//     cin >> n >> k;
//     for(int i = 1; i < n; i++)
//     {
//         int u , v , w;
//         cin >> u >> v >> w;
//         u++ , v++;
//         g[u].push_back({v , w});
//         g[v].push_back({u , w});
//     }
    
//     dfs_build(1 , 1);
//     dfs(1 , 1);
//     cout << ans << '\n';
// }

// // testing

// signed main() 
// {
//     //solve();
//     return 0;
// }

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