Submission #849550

#	Time	Username	Problem	Language	Result	Execution time	Memory
849550		manhtuan22007	Race (IOI11_race)	C++14	100 / 100	418 ms	106780 KiB

race

#include <bits/stdc++.h>

#define name ""
//#define int long long
#define ll long long
using namespace std;

const int maxn = 2e5 + 10;

int n , k , h[maxn] , cost[maxn] , res = -1;
vector<vector<pair<int , int>>> g(maxn);
vector<map<ll , ll>> mp;

void pre(int u , int p , int sum , int dep){
	mp[u][sum] = dep;
	cost[u] = sum;
	h[u] = dep;
	for(auto e : g[u]){
		int v = e.first;
		if(v == p) continue;
		
		pre(v , u , sum + e.second , dep + 1);
	}
}

void dfs(int u , int p){
	for(auto e : g[u]){
		int v = e.first;
		if(v == p) continue;
		dfs(v , u);
		if(mp[u].size() < mp[v].size()) swap(mp[u] , mp[v]);
		for(auto x : mp[v]){
			auto it = mp[u].find(k + 2 * cost[u] - x.first);
			if(it != mp[u].end()){
				int c = it->second + x.second - 2 * h[u];
				res = (res == -1 ? c : min(res , c));
			}
		}
		for(auto x : mp[v]){
			auto it = mp[u].find(x.first);
			if(it == mp[u].end()) mp[u].insert(x);
			else mp[u][x.first] = min(mp[u][x.first] , x.second); // uu tien h cao nhat 
		}
	}
}

int best_path(int nn , int kk , int h[][2] , int l[]){
	n = nn , k = kk;
	// cout <<  n <
	mp.resize(n + 10);
	for(int i = 0 ; i < n - 1 ; i ++){
		int u = h[i][0] , v = h[i][1];
		++u , ++v;
		g[u].push_back({v , l[i]});
		g[v].push_back({u , l[i]});
	}
	pre(1 , 0 , 0 , 0);
	dfs(1 , 0);
	return res;
}

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