제출 #1228644

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

race

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

using namespace std;
using ll = long long;

#define all(x) begin(x), end(x)
//#define int ll
const int NN = 2e5+1;

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

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) {
	int big = -1;
	for (auto i: g[a])
		if (i.first != p && (!~big || sz[i.first] > sz[big]))big = i.first;
	
	if (~big)dfs(big, a), mp[a] = mp[big];
	else mp[a] = new map<ll, int> ();

	(*mp[a])[sum[a]] = dep[a];
	if (mp[a]->find(kk+sum[a]) != mp[a]->end())res = min(res, (*mp[a])[kk+sum[a]]-dep[a]);
	
	for (auto [i, w]: g[a]) {
		if (i == p || i == big)continue;
		dfs(i, a);
		for (auto [j, d]: *mp[i]) {
			ll aa = kk-(j-sum[a])+sum[a];
			if (mp[a]->find(aa) != mp[a]->end())res = min(res, (*mp[a])[aa]+d-2*dep[a]);
		}
		
		for (auto [j, d]: *mp[i]) {
			if (mp[a]->find(j) == mp[a]->end())(*mp[a])[j] = d;
			else (*mp[a])[j] = min((*mp[a])[j], d);
		}
	}
}
 
int best_path(int n, int k, int h[][2], int l[]) {
	
	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]});
	}
	mp.assign(n, {});
	
	res = NN;
	calc();
	dfs();
	for (int i = 0; i < n; ++i) {
		g[i].clear();
	}
	return (res==NN?-1:res);
}

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