제출 #1228495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228495		tkm_algorithms	경주 (Race) (IOI11_race)	C++20	0 / 100	2 ms	5184 KiB

race

/**
*    In the name of Allah
*    We are nothing and you're everything
*    Ya Muhammad!
**/
#include <bits/stdc++.h>
#include "race.h"

using namespace std;
using ll = long long;

#define all(x) begin(x), end(x)
#define int ll
const ll N = 2e5+5;

vector<pair<int, int>> g[N];
int sz[N], dep[N], sum[N];
vector<int> *vec[N];
map<int, int> *mp[N];
ll res = N;

void calc(int a = 0, int p = 0) {
	sz[a] = 1;
	for (auto i: g[a]) {
		if (i.first == p)continue;
		dep[i.first] = dep[a]+1;
		sum[i.first] = sum[a]+i.second;
		calc(i.first, a);
		sz[a] += sz[i.first];
	}
}

int kk;

void dfs(int a = 0, int p = 0, bool ok = true) {
	int mx = 0, big = -1;
	for (auto i: g[a]) {
		if (i.first != p && sz[i.first] > mx)mx = sz[i.first], big = i.first;
	}
	
	for (auto i: g[a]) {
		if (i.first != p && i.first != big)dfs(i.first, a, 0);
	}
	
	if (~big) {
		dfs(big, a, 1), mp[a] = mp[big], vec[a] = vec[big];
	}
	else mp[a] = new map<int, int>, vec[a] = new vector<int>;
	
	vec[a]->push_back(a);
	
	(*mp[a])[sum[a]] = ((*mp[a])[sum[a]]==0?dep[a]: min(dep[a], (*mp[a])[sum[a]]));
	
	map<int, int> temp = (*mp[a]);
	if (temp[kk+sum[a]] != 0)res = min(res, temp[kk+sum[a]]-dep[a]);
	for (auto i: g[a]) {
		if (i.first == p || i.first == big)continue;
		for (auto j: *vec[i.first]) {
			vec[a]->push_back(j);
			int h = sum[j]-sum[a];
			if ((*mp[a])[sum[j]] == 0)(*mp[a])[sum[j]] = dep[j];
			else ((*mp[a])[sum[j]]) = min((*mp[a])[sum[j]], dep[j]);
			if (kk-h < 0)continue;
			if (temp[sum[a]+kk-h] == 0)continue;
			else res = min(res, temp[sum[a]+kk-h]+dep[j]-2*dep[a]);
		}
		temp = (*mp[a]);
	}
	
	if (!ok) {
		for (auto i: *vec[a])(*mp[a])[sum[i]] = 0;
	}
}
 
int32_t best_path(int32_t n, int32_t k, int32_t h[][2], int32_t l[]) {
	for (int i = 0; i < n; ++i) {
		g[i].clear();
		(*mp[i]).clear();
		(*vec[i]).clear();
	}
	dep[0] = 1;
	kk = k;
	
	for (int i = 0; i < n-1; ++i) {
		g[h[i][0]].push_back({h[i][1], l[i]});
		g[h[i][1]].push_back({h[i][0], l[i]});
	}
	
	calc();
	dfs();
	
	return (int32_t)(res==N?-1:res);
}

//int main() {
	//int n; cin >> n >> k;
	//for (int i = 0; i < n-1; ++i) {
		//int a, b, w; cin >> a >> b >> w;
		//g[a].push_back({b, w});
		//g[b].push_back({a, w});
	//}
	
	//dep[0] = 1;
	//calc();
	//dfs();
	//cout << res;
//}

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