Submission #1118520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118520		MateiKing80	Race (IOI11_race)	C++14	9 / 100	146 ms	41532 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;
    }
    if(fmax == 0)
    {
        //cout << nod << '\n';
        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(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)
            {
                //cout << "MadMorb: " << l.fr << " " << l.sc.fr << " " << l.sc.sc << '\n';
                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';*/
}

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;
}

Compilation message (stderr)

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

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