Submission #674887

#	Time	Username	Problem	Language	Result	Execution time	Memory
674887		penguin133	Race (IOI11_race)	C++14	100 / 100	433 ms	114120 KiB

race

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

typedef long long ll;
#define pi pair<ll, ll>
#define pii pair<ll, pi>
#define fi first
#define se second

set<pi>s[200005];
ll os[200005], os2[200005];
vector<pi>v[200005];
ll n, k;
ll ans = 1e18;
void dfs(int x, int par){
	s[x].insert({0, 0});
	for(auto [i, j] : v[x]){
		if(i == par)continue;
		dfs(i, x);
		os[i] += j;
		os2[i]++;
		if(s[i].size() > s[x].size())swap(s[i], s[x]), swap(os[i], os[x]), swap(os2[i], os2[x]);
		for(auto [el, el2] : s[i]){
			int real = el + os[i];
			int needed = k - real - os[x];
			auto it = s[x].lower_bound({needed, -1e9});
			if(it == s[x].end())continue;
			pi tmp = *it;
			if(tmp.fi == needed)ans = min(ans, os2[x] + os2[i] + el2 + tmp.se);
		}
		for(auto [el, el2] : s[i]){
			int real = el + os[i], real2 = el2 + os2[i];
			real -= os[x], real2 -= os2[x];
			s[x].insert({real, real2});
		}
	}
	//cout << x << '\n';
	//for(auto [i, j] : s[x])cout << i << " " << j << '\n';
	//cout << os[x] << " " << os2[x] << '\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++){
		v[H[i][0]].push_back({H[i][1], L[i]});
		v[H[i][1]].push_back({H[i][0], L[i]});
	}
	dfs(0, -1);
  if(ans == 1e18)return -1;
  else return (int32_t)ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:18:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |  for(auto [i, j] : v[x]){
      |           ^
race.cpp:24:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |   for(auto [el, el2] : s[i]){
      |            ^
race.cpp:32:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |   for(auto [el, el2] : s[i]){
      |            ^

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