Submission #1091811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091811		Luca1234	Race (IOI11_race)	C++14	100 / 100	337 ms	82972 KiB

race

#include <bits/stdc++.h>
using namespace std;

const int nmax=2e5+3;
vector <pair <int, int> > v[nmax];
map <int, int> m[nmax];
int k, ans=nmax;

void dfs(int nod, int parent, int d, int h)
{
    m[nod][d]=h;
    for(auto [i, cost]:v[nod])
    {
        if(i!=parent)
        {
            dfs(i, nod, d+cost, h+1);
            if(m[i].size()>m[nod].size()) swap(m[i], m[nod]);
            for(auto [dist, he]:m[i])
            {
                int caut=k+2*d-dist;
                if(m[nod].count(caut))
                {
                    ans=min(ans, he+m[nod][caut]-2*h);
                }
            }
            for(auto [dist, he]:m[i])
            {
                if(m[nod].count(dist))
                {
                    m[nod][dist]=min(m[nod][dist], he);
                }
                else m[nod][dist]=he;
            }
        }
    }
}

long long best_path(int n, int k, int h[][2], int l[])
{
    ::k=k;
    for(int i=0; i<n-1; i++)
    {
        int a=h[i][0], b=h[i][1];
        v[a].push_back({b, l[i]});
        v[b].push_back({a, l[i]});
    }
    dfs(0, -1, 0, 1);
    if(ans==nmax) return -1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int, int, int)':
race.cpp:12:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   12 |     for(auto [i, cost]:v[nod])
      |              ^
race.cpp:18:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |             for(auto [dist, he]:m[i])
      |                      ^
race.cpp:26:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |             for(auto [dist, he]:m[i])
      |                      ^

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