Submission #486783

#	Time	Username	Problem	Language	Result	Execution time	Memory
486783		status_coding	Race (IOI11_race)	C++14	100 / 100	382 ms	89296 KiB

race

#include <bits/stdc++.h>

using namespace std;

struct mulS
{
    map<int, int> m;
    int dif=0;

    mulS(){};
    mulS(int d)
    {
        m[0]=d;
    }
};
struct nodS
{
    int d;
    mulS *mul;
    vector<pair<int, int>> v;
};

int n,k,ans;
nodS nod[200005];

int getVal(mulS *a, int val)
{
    val -= a->dif;

    if(a->m.find(val) == a->m.end())
        return -1;

    return a->m[val];
}
void mergeMul(int d, mulS *&a, mulS *& b)
{
    if(a->m.size() < b->m.size())
        swap(a, b);

    for(auto it : b->m)
    {
        int trVal = it.first + b->dif;

        int oD = getVal(a, k - trVal);
        if(oD != -1)
            ans = min(ans, it.second + oD - 2*d);
    }

    for(auto it : b->m)
    {
        int nVal = it.first + b->dif - a->dif;

        if(a->m.find(nVal) == a->m.end() || a->m[nVal] > it.second)
            a->m[nVal] = it.second;
    }
}

void dfs(int p, int par)
{
    nod[p].d = nod[par].d+1;
    nod[p].mul = new mulS(nod[p].d);

    for(auto it : nod[p].v)
    {
        if(it.first == par)
            continue;

        dfs(it.first, p);
        nod[it.first].mul->dif += it.second;

        mergeMul(nod[p].d, nod[p].mul, nod[it.first].mul);
    }

    /*
    if(p >= 9)
    {
        cout<<p<<":\n";
        for(auto it : nod[p].mul->m)
            cout<<it.first + nod[p].mul->dif<<' '<<it.second<<'\n';
        cout<<'\n';
    }
    */
}

int best_path(int N, int K, int h[][2], int l[])
{
    n=N;
    k=K;

    for(int i=0;i<n-1;i++)
    {
        int x = h[i][0] + 1;
        int y = h[i][1] + 1;

        nod[x].v.push_back({y, l[i]});
        nod[y].v.push_back({x, l[i]});
    }

    ans=1e9;
    dfs(1, 0);

    if(ans == 1e9)
        return -1;

    return ans;
}

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