제출 #1163351

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163351		DangKhoizzzz	경주 (Race) (IOI11_race)	C++17	100 / 100	307 ms	79420 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 = 1e18;
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);
    }
}

int curnode = 0;

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

    for(pii tmp: b)
    {
        ll v1 = tmp.fi;
        ll v2 = tmp.se;
        if(a.count(k - v1 + 2ll*reqdepth))
        {
            ans = min(ans , a[k - v1 + 2ll*reqdepth] + v2 - 2ll*reqh);
        }
    }

    for(pii tmp: b)
    {
        ll v1 = tmp.fi;
        ll v2 = tmp.se;
        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];

    curnode = 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);


//     if(ans == INF) cout << -1 << '\n';
//     else cout << ans << '\n';
// }

// // testing

// signed main()
// {
//     //freopen("ok.inp","r" , stdin);
//     solve();
//     return 0;
// }

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