제출 #1228575

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228575		tkm_algorithms	Race (IOI11_race)	C++20	9 / 100	3099 ms	57972 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 int NN = 2e5+5;

vector<pair<ll, int>> g[NN];
int sz[NN], dep[NN];
ll sum[NN];
vector<int> *vec[NN];
map<ll, int> *mp[NN];
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, 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<ll, 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<ll, 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.find(sum[a]+kk-h) == temp.end())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;
	}
}
 
int best_path(int n, int k, int h[][2], int l[]) {
	
	for (int i = 0; i < n; ++i) {
		g[i].clear();
		mp[i] = new map<ll, int>;
		vec[i] = new vector<int>;
	}
	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]});
	}
	
	res = NN;
	calc();
	dfs();
	return (res==NN?-1:res);
}

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