Submission #1118504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118504		MateiKing80	Race (IOI11_race)	C++17	0 / 100	3 ms	18768 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;
#define fr first
#define sc second

const int N = 200000;
int k, sz[N + 5], addlg[N + 5], addnr[N + 5], ans = 1e9;
vector<pii> vec[N + 5];
map<int, pii> mp[N + 5];


void dfs(int nod, int papa)
{
    int fmax = 0, lg;
    sz[nod] = 1;
    for(auto [i, j] : vec[nod])
    {
        if(i == papa)
            continue;
        dfs(i, nod);
        sz[nod] += sz[i];
        if(sz[fmax] < sz[i])
            fmax = i, lg = j;
    }
    mp[nod][0] = {0, 1};
    if(fmax == 0)
        return;
    swap(mp[nod], mp[fmax]);
    swap(addlg[nod], addlg[fmax]);
    swap(addnr[nod], addnr[fmax]);
    addlg[nod] += lg;
    addnr[nod] ++;
    for(auto [i, j] : vec[nod])
    {
        if(i == papa)
            continue;
        addlg[i] += j;
        addnr[i] += 2;
        for(auto l : mp[i])
            if(l.sc.sc == 1)
            {
                if(k >= addlg[nod] + addlg[i] + l.fr && mp[nod][k - addlg[nod] - addlg[i] - l.fr].sc == 1)
                    ans = min(ans, l.sc.fr + addnr[nod] + addnr[i] + mp[nod][k - addlg[nod] - addlg[i] - l.fr].fr);
            }
        for(auto l : mp[i])
            if(l.sc.sc == 1)
            {
                if(mp[nod][l.fr + addlg[i] - addlg[nod]].sc == 1)
                    mp[nod][l.fr + addlg[i] - addlg[nod]] = {min(mp[nod][l.fr + addlg[i] - addlg[nod]].fr, l.sc.fr + addlg[i] - addlg[nod]), 1};
            }
    }
    if(mp[nod][k - addlg[nod]].sc == 1)
        ans = min(ans, mp[nod][k - addlg[nod]].fr + addnr[nod]);
    mp[nod][-addlg[nod]] = {-addnr[nod], 1};
}

int best_path(int n, int K, int h[][2], int l[])
{
    k = K;
    if(k == 0)
        return 0;
    for(int i = 0; i < n - 1; i ++)
    {
        vec[h[i][0] + 1].push_back({h[i][1] + 1, l[i]});
        vec[h[i][1] + 1].push_back({h[i][0] + 1, l[i]});
    }
    dfs(1, 0);
    if(ans == 1e9)
        return -1;
    return ans;
}

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