Submission #551187

#	Time	Username	Problem	Language	Result	Execution time	Memory
551187		ymm	Race (IOI11_race)	C++17	100 / 100	862 ms	60764 KiB

race

///
///   There's a reason for your defeat, DIO. One simple reason...
///   You pissed me off.
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

#ifndef DARD
#include "race.h"
#endif

const int N = 200'010;
vector<pll> A[N];
bool block[N];
int cnt[N];
int n, k;

int dfs_cnt_rem(int v, int p)
{
	cnt[v] = 1;
	Loop (i,0,A[v].size()) {
		if (block[A[v][i].first]) {
			swap(A[v][i], A[v].back());
			A[v].pop_back();
			--i;
		} else if (A[v][i].first != p) {
			cnt[v] += dfs_cnt_rem(A[v][i].first, v);
		}
	}
	return cnt[v];
}

int dfs_cent(int v, int p, int cnt)
{
	for (auto [u, _] : A[v]) {
		if (u == p)
			continue;
		if (::cnt[u] > cnt/2)
			return dfs_cent(u, v, cnt);
	}
	return v;
}

void dfs_len(int v, int p, pll cur, vector<pll>& vec)
{
	vec.push_back(cur);
	for (auto [u, w] : A[v]) {
		if (u == p)
			continue;
		dfs_len(u, v, {cur.first+w, cur.second+1}, vec);
	}
}

int solve(int v)
{
	dfs_cnt_rem(v, -1);
	v = dfs_cent(v, -1, cnt[v]);
	map<ll, int> mp; mp[0] = 0;
	vector<pll> vec;
	int ans = N;
	for (auto [u, w] : A[v]) {
		vec.clear();
		dfs_len(u, v, {w, 1}, vec);
		for (auto [x, y] : vec) {
			auto it = mp.find(k-x);
			if (it != mp.end())
				ans = min(ans, (int)(y + it->second));
		}
		for (auto [x, y] : vec) {
			int &z = mp[x];
			if (!z || z > y)
				z = y;
		}
	}
	block[v] = 1;
	for (auto [u, _] : A[v])
		ans = min(ans, solve(u));
	return ans;
}

int best_path(int n, int k, int h[][2], int l[])
{
	::n = n; ::k = k;
	Loop (i,0,n-1) {
		A[h[i][0]].push_back({h[i][1], l[i]});
		A[h[i][1]].push_back({h[i][0], l[i]});
	}
	int ans = solve(0);
	return ans == N? -1: ans;
}

#ifdef DARD
int main()
{
//	int constexpr n = 4;
//	int constexpr k = 3;
//	int h[n-1][2] = {{0, 1}, {1, 2}, {1, 3}};
//	int l[n-1] = {1, 2, 4};
	int constexpr n = 3;
	int constexpr k = 3;
	int h[n-1][2] = {{0, 1}, {1, 2}};
	int l[n-1] = {1, 1};
//	int constexpr n = 11;
//	int constexpr k = 12;
//	int h[n-1][2] = {{0, 1}, {0, 2}, {2, 3}, {3, 4}, {4, 5}, {0, 6}, {6, 7}, {6, 8}, {8, 9}, {8, 10}};
//	int l[n-1] = {3, 4, 5, 4, 6, 3, 2, 5, 6, 7};
	cout << best_path(n, k, h, l) << '\n';
}
#endif

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