Submission #1118524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118524		MateiKing80	Race (IOI11_race)	C++14	100 / 100	762 ms	157772 KiB

race

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

using namespace std;

using ll = long long;
#define int ll

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;
    }
    if(fmax == 0)
    {
        mp[nod][0] = {0, 1};
        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;
        if(i == fmax)
            continue;
        addlg[i] += j;
        addnr[i] += 1;
        for(auto l : mp[i])
            if(l.sc.sc == 1)
            {
                if(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 + addnr[i] - addnr[nod]), 1};
                else
                    mp[nod][l.fr + addlg[i] - addlg[nod]] = {l.sc.fr + addnr[i] - addnr[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};
    /*cout << nod << " " << addlg[nod] << " " << addnr[nod] << '\n';
    for(auto i : mp[nod])
        if(i.sc.sc == 1)
            cout << i.fr << " " << i.sc.fr << '\n';*/
}

signed best_path(signed n, signed K, signed h[][2], signed 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;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(ll, ll)':
race.cpp:23:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |     for(auto [i, j] : vec[nod])
      |              ^
race.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for(auto [i, j] : vec[nod])
      |              ^

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