제출 #1283226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283226		nemkho	경주 (Race) (IOI11_race)	C++17	100 / 100	1166 ms	69220 KiB

race

#include <bits/stdc++.h>
#define ll long long
#define pr pair <ll, int>
#define fi first
#define se second
using namespace std;
const int N = 2e5 + 5;
int n, k, sta[N], en[N], tour[N], large[N], cnt, ans = 1e9, h[N];
ll dist[N];
vector <pr> a[N];
map<ll, multiset<int>> mp;


int dfs (int u, int pre)
{
    int cur_siz = 1;
    int max_siz = 0;
    sta[u] = ++cnt;
    tour[cnt] = u;
    for (pr i : a[u])
    {
        int v = i.se;
        ll w = i.fi;
        if (v == pre)
            continue;
        dist[v] = dist[u] + w;
        h[v] = h[u] + 1;
        int siz = dfs(v, u);
        if (siz > max_siz)
        {
            large[u] = v;
            max_siz = siz;
        }
        cur_siz += siz;
    }
    en[u] = cnt;
    return cur_siz;
}

void add (int u)
{
    mp[dist[u]].insert(h[u]);
}

void doo(int u, int lca)
{
    ll d = k - dist[u] + 2*dist[lca];
    if (mp.count(d) && mp[d].size() > 0)
    {
        int haha = h[u] + *mp[d].begin() - 2*h[lca];
        ans = min(ans, haha);
    }
    if (dist[u] - dist[lca] == k)
        ans = min(ans, h[u] - h[lca]);
}

void del (int u)
{
    mp[dist[u]].erase(mp[dist[u]].find(h[u]));
}

void Sack (int u, int pre, bool keep)
{
    for (pr i : a[u])
    {
        int v = i.se;
        if (v == pre || v == large[u])
            continue;
        Sack(v, u, 0);
    }
    if (large[u] != -1)
        Sack(large[u], u, 1);
    add(u);
    for (pr i : a[u])
    {
        int v = i.se;
        if (v == pre || v == large[u])
            continue;
        for (int i = sta[v]; i <= en[v]; i++)
            doo(tour[i], u);
        for (int i = sta[v]; i <= en[v]; i++)
            add(tour[i]);
    }
    doo(u, u);
    if (!keep)
    {
        for (int i = sta[u]; i <= en[u]; i++)
            del(tour[i]);
    }
}

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]});
    }
    memset(large, -1, sizeof(large));
    dfs(0, -1);
    Sack(0, -1, 1);
    return (ans == 1e9 ? -1 : ans);
}

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