제출 #419305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
419305		iulia13	경주 (Race) (IOI11_race)	C++14	100 / 100	1664 ms	50184 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int N = 2e5 + 5;
const int K = 1e6 + 5;
struct ura{
    int x, c;
};
vector <ura> g[N];
int vc[K];
int sz[N], viz[N];
int n, k; int minim = K;
void dfsSize(int nod, int dad = -1)
{
    sz[nod] = 1;
    for (auto son : g[nod])
    {
        if (son.x == dad || viz[son.x])
            continue;
        dfsSize(son.x, nod);
        sz[nod] += sz[son.x];
    }
}
map <int, int> mp2;
int centroid(int nod, int dad, int newN)
{
    for (auto son : g[nod])
    {
        if (son.x == dad || viz[son.x])
            continue;
        if (sz[son.x] > newN / 2)
            return centroid(son.x, nod, newN);
    }
    return nod;
}
void dfs(int nod, int dad, int sum, int l)
{
    if (sum > k)
        return;
    if (mp2[sum])
        mp2[sum] = min(mp2[sum], l);
    else
        mp2[sum] = l;
    for (auto son : g[nod])
    {
        if (son.x == dad || viz[son.x])
            continue;
        dfs(son.x, nod, sum + son.c, l + 1);
    }
}
void divide(int root)
{
    dfsSize(root);
    int mid = centroid(root, -1, sz[root]);
    viz[mid] = 1;
    map <int, int> mp;
    for (auto son : g[mid])
    {
        int x = son.x;
        if (viz[x])
            continue;
        mp2.clear();
        dfs(x, mid, son.c, 1);
        for (auto it : mp2)
        {
            if (it.first == k)
                minim = min(minim, it.second);
            if (mp.count(k - it.first) == 0)
                continue;
            minim = min(minim, it.second + mp[k - it.first]);
        }
        for (auto it : mp2)
        {
            int beb = it.first;
            if (mp[beb] == 0)
                mp[beb] = mp2[beb];
            else
                mp[beb] = min(mp[beb], mp2[beb]);
        }
    }
    for (auto son : g[mid])
        if (viz[son.x] == 0)
            divide(son.x);
}
int best_path(int nn, int kk, int h[][2], int l[])
{
    int i;
    n = nn;
    k = kk;
    for (i = 0; i < n - 1; i++)
    {
        int a = h[i][0];
        int b = h[i][1];
        g[a].push_back({b, l[i]});
        g[b].push_back({a, l[i]});
    }
    divide(0);
    if (minim == K)
        minim = -1;
    return minim;
}

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