제출 #1017000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1017000		xnqs	경주 (Race) (IOI11_race)	C++17	100 / 100	233 ms	71084 KiB

race

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <set>

#include "race.h"

int gs, tgt;
std::vector<std::vector<std::pair<int,int>>> adj_list;
int depth[200005];
int64_t dist[200005];

void dfs1(int k, int p) {
	for (const auto& [i, w] : adj_list[k]) {
		if (i!=p) {
			depth[i] = depth[k]+1;
			dist[i] = dist[k] + w;
			dfs1(i,k);
		}
	}
}

std::set<std::pair<int64_t,int>> dfs2(int k, int p, int& ans) {
	std::set<std::pair<int64_t,int>> ret;
	ret.emplace(dist[k], depth[k]);

	for (const auto& [i, w] : adj_list[k]) {
		if (i!=p) {
			auto tmp = dfs2(i,k,ans);
			if (ret.size()<tmp.size()) {
				std::swap(ret,tmp);
			}

			for (const auto& a : tmp) {
				if (a.first-dist[k]==tgt) {
					ans = std::min(ans, a.second-depth[k]);
				}

				auto b = ret.lower_bound(std::pair<int64_t,int>(tgt-a.first+2*dist[k],0));
				if (b==ret.end()) {
					continue;
				}
				if (b->first==tgt-a.first+2*dist[k]) {
					ans = std::min(ans, a.second+b->second-2*depth[k]);
				}
			}

			for (const auto& it : tmp) {
				ret.emplace(it);
			}
		}
	}

	return ret;
}

int best_path(int N, int K, int H[][2], int L[]) {
	gs = N;
	tgt = K;
	adj_list.clear(); adj_list.resize(gs+1);

	for (int i = 0; i < gs-1; i++) {
		adj_list[H[i][0]].emplace_back(H[i][1], L[i]);
		adj_list[H[i][1]].emplace_back(H[i][0], L[i]);
	}

	dfs1(0,-1);
	int ret = 0x3f3f3f3f; dfs2(0,-1,ret);

	if (ret == 0x3f3f3f3f) {
		return -1;
	}
	return ret;
}

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