제출 #672381

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
672381		vjudge1	경주 (Race) (IOI11_race)	C++17	0 / 100	4 ms	5012 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define el '\n'
#define FIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;


const int N = 2e5 + 10;

bool vis[N];
int sz[N], k;
map<ll, int> mn;
ll ans = LLONG_MAX;
vector<pair<int, ll>> G[N];

int dfsSZ(int node, int par = -1)
{
    sz[node] = 1;
    for(auto &[ch, w]: G[node])
    {
        if(ch == par || vis[node])
            continue;
        sz[node] += dfsSZ(ch, node);
    }
    return sz[node];
}

int getCentroid(int node, int par, int &n)
{
    for(auto &[ch, w]: G[node])
    {
        if(ch == par || vis[ch])
            continue;

        if(sz[ch] << 1 > n)
            return getCentroid(ch, node, n);
    }
    return node;
}

void dfs(int node, int par, int dist, int dep)
{
    if(mn.count(dist))
        mn[dist] = min(mn[dist], dep);
    else
        mn[dist] = dep;

    for(auto &[ch, w]: G[node])
    {
        if(ch == par || vis[ch])
            continue;
        dfs(ch, node, dist + w, dep + 1);
    }
}

ll solve(int node, int par, int dist, int dep)
{
    if(dist > k)
        return LLONG_MAX;

    ll ret = LLONG_MAX;
    if(mn.count(k - dist) && mn[k - dist])
        ret = mn[k - dist] + dep;

    for(auto &[ch, w]: G[node])
    {
        if(ch == par || vis[ch])
            continue;
        ret = min(ret, solve(ch, node, dist + w, dep + 1));
    }
    return ret;
}

void solveSubTree(int centroid, int par, int d)
{

    for(auto &[ch, w]: G[centroid])
    {
        if(ch == par || vis[ch])
            continue;

        ans = min(ans, solve(ch, centroid, d + w, 1));
        dfs(ch, centroid, d + w, 1);
    }
    mn.clear();
}

void decompose(int node, int par, int d)
{
    dfsSZ(node, par);
    int centroid = getCentroid(node, par, sz[node]);

    vis[centroid] = true;
    solveSubTree(centroid, par, d);
    for(auto &[ch, w]: G[centroid])
    {
        if(ch == par || vis[ch])
            continue;
        decompose(ch, centroid, d + w);
    }
}

int best_path(int n, int K, int H[][2], int L[])
{
    k = K;
    for(int i = 0; i < n - 1; i++)
    {
        G[H[i][0]].emplace_back(H[i][1], L[i]);
        G[H[i][1]].emplace_back(H[i][0], L[i]);
    }
    decompose(1, -1, 0);
    if(ans == LLONG_MAX)
        return -1;
    else
        return ans;
}

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