제출 #872601

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
872601		andre_stan	경주 (Race) (IOI11_race)	C++14	0 / 100	3 ms	16728 KiB

race

///val[i] nivelul la care exista suma i
///dp[i] nr minim de muchii de a forma suma i

#include <iostream>
#include <vector>

using namespace std;

using ll = long long;
using pa = pair <ll, ll>;

const ll INF = 1e18;
const int N = 2e5;
const int M = 1e6;
ll siz[N + 1], removed[N + 1], tata_c[N + 1], dp[M + 1], h[N + 1][2], l[N + 1], val[M + 1];

vector <pa> g[N + 1];

int n, x, y, k, dep;

void dfs (int node, int parent)
{
    siz[node] = 1;
    for (auto it : g[node])
        if (it.first != parent && !removed[it.first])
        {
            dfs (it.first, node);
            siz[node] += siz[it.first];
        }
}

int centroid (int node, int parent, int len)
{
    for (auto it : g[node])
        if (it.first != parent && !removed[it.first])
        {
            if (siz[it.first] > (len / 2))return centroid (it.first, node, len);
        }
    return node;
}

ll dfs1 (int node, int parent, ll cost, int edges, int dep, vector <pa> &v)
{
    ll ans = INF;
    ll ramas = k - cost;
    if (ramas >= 0ll && val[ramas] == dep)
        ans = min (ans, edges + dp[ramas]);
    else if (ramas > 0ll)
    {
        v.push_back({cost, edges});
        for (auto it : g[node])
            if (it.first != parent && !removed[it.first])
                ans = min (ans, dfs1 (it.first, node, cost + it.second, edges + 1, dep, v));
    }
    return ans;
}

ll centroid_decomp (int node, int parent)
{
    ll ans = INF;
    dfs (node, parent);
    int len = siz[node];
    int c = centroid (node, parent, len);
    removed[c] = 1;
    tata_c[c] = parent;
    ++dep;
    dp[0] = 0;
    val[0] = dep;
    ///fac pentru un subarbore care are lca centroidul meu
    for (auto it : g[c])
        if (!removed[it.first])
        {
            vector <pa> v;
            v.clear();
            ans = min (ans, dfs1 (it.first, c, it.second, 1, dep, v));
            for (auto it1 : v)
                if (val[it1.first] != dep || (val[it1.first] == dep && dp[it1.first] > it1.second))
                {
                    val[it1.first] = dep;
                    dp[it1.first] = it1.second;
                }
        }
    for (auto it : g[c])
        if (!removed[it.first])
            ans = min (ans, centroid_decomp (it.first, c));
    return ans;
}

int best_path (int n, int k, int h[][2], int l[])
{
    for (int i = 0; i < n - 1; ++i)
    {
        g[h[i][0]].push_back({h[i][1], l[i]});
        g[h[i][1]].push_back ({h[i][0], l[i]});
    }
    ll ans = INF;
    ans = min (ans, centroid_decomp(0, -1));
    if (ans == INF)
        ans = -1;
    return ans;
}
/*
int main()
{

    cin >> n >> k;
    for (int i = 0; i < n - 1; ++i)
        cin >> h[i][0] >> h[i][1];
    for (int i = 0; i < n - 1; ++i)
        cin >> l[i];
    cout << best_path (n, k, h, l) << '\n';
    return 0;
}

*/

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