Submission #399100

#	Time	Username	Problem	Language	Result	Execution time	Memory
399100		usuyus	Race (IOI11_race)	C++14	43 / 100	406 ms	94908 KiB

race

// solution

#include <bits/stdc++.h>
#define N_ 200005
#define INF ((ll)1e18+5)
using namespace std;
using ll = long long;

struct Edge { ll to, cost; };

ll n, k, len[N_], dep[N_], ans;
vector<Edge> tree[N_];
map<int, ll> mp[N_];

void dfs(int nd, int par) {
	mp[nd][len[nd]] = dep[nd];

	for (Edge e : tree[nd]) {
		if (e.to == par) continue;
		dep[e.to] = dep[nd] + 1;
		len[e.to] = len[nd] + e.cost;
		dfs(e.to, nd);

		if (mp[nd].size() < mp[e.to].size()) {
			swap(mp[nd], mp[e.to]);
		}

		for (auto [x, d] : mp[e.to]) {
			ll y = k + 2 * len[nd] - x;
			if (mp[nd].count(y)) {
				ans = min(ans, d + mp[nd][y] - 2 * dep[nd]);
			}

			if (!mp[nd].count(x)) mp[nd][x] = d;
			else mp[nd][x] = min(mp[nd][x], d);
		}
	}
}

int best_path(int N, int K, int H[][2], int L[]) {
	n = N;
	k = K;

	for (int i=0; i<n-1; i++) {
		tree[H[i][0]].push_back({H[i][1], L[i]});
		tree[H[i][1]].push_back({H[i][0], L[i]});
	}

	ans = INF;
	dfs(0, -1);
	return ans == INF ? -1 : ans;
}

// grader

// // #include "race.h"
// #include <stdio.h>
// #include <stdlib.h>

// #define MAX_N 500000

// static int N, K;
// static int H[MAX_N][2];
// static int L[MAX_N];
// static int solution;

// inline 
// void my_assert(int e) {if (!e) abort();}

// void read_input()
// {
// 	int i;
// 	my_assert(2==scanf("%d %d",&N,&K));
// 	for(i=0; i<N-1; i++)
// 		my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
// 	my_assert(1==scanf("%d",&solution));
// }

// int main()
// {
// 	freopen("race.gir", "r", stdin);
// 	int ans;
// 	read_input();
// 	ans = best_path(N,K,H,L);
// 	if(ans==solution)
// 		printf("Correct.\n");
// 	else
// 		printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

// 	return 0;
// }

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:28:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |   for (auto [x, d] : mp[e.to]) {
      |             ^

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