Submission #872580

#	Time	Username	Problem	Language	Result	Execution time	Memory
872580		andre_stan	Race (IOI11_race)	C++14	0 / 100	2 ms	14684 KiB

race

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

#include <iostream>
#include <set>
#include <vector>

using namespace std;

using pa = pair <int, int>;

const int INF = 1e9;
const int N = 2e5;
const int M =  1e6;
int 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;
}

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

int centroid_decomp (int node, int parent)
{
    int 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;
            ans = min (ans, dfs1 (it.first, c, it.second, 1, dep, v));
            for (auto it : v)
                if (val[it.first] != dep || (val[it.first] == dep && dp[it.first] > it.second))
                {
                    val[it.first] = dep;
                    dp[it.first] = it.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[N + 1][2], int l[N + 1])
{
    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]});
    }
    int 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