제출 #551211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
551211		alireza_kaviani	경주 (Race) (IOI11_race)	C++17	9 / 100	273 ms	54224 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define X     first
#define Y     second
#define SZ(x) ll((x).size())

const ll MAXN = 2e5 + 10;
const ll INF = 1e18;

ll n , k , ans = INF , H[MAXN] , dist[MAXN];
vector<pii> adj[MAXN];
map<ll , ll> mn[MAXN];

void DFS(int v , int p = -1){
	for(pii i : adj[v]){
		int u = i.X , w = i.Y;
		if(u == p)	continue;
		H[u] = H[v] + 1;
		dist[u] = dist[v] + w;
		DFS(u , v);
		if(SZ(mn[u]) > SZ(mn[v])){
			mn[v].swap(mn[u]);
		}
		for(auto &i : mn[u]){
			ll D = k + dist[v] * 2 - i.X;
			if(mn[v][D] != 0){
				ans = min(ans , i.Y + mn[v][D] - 2 * H[v]);
			}
		}
		for(auto &i : mn[u]){
			if(mn[v][i.X] == 0)	mn[v][i.X] = i.Y;
			mn[v][i.X] = min(mn[v][i.X] , i.Y);
		}
	}
	ll D = k + dist[v];
	if(mn[v][D] != 0){
		ans = min(ans , mn[v][D] - H[v]);
	}
	if(mn[v][dist[v]] == 0)	mn[v][dist[v]] = H[v];
	mn[v][dist[v]] = min(mn[v][dist[v]] , H[v]);
}

int best_path(int N, int K, int H[][2], int L[]){
	n = N; k = K;
	for(int i = 0 ; i + 1 < n ; i++){
		int v = H[i][0] , u = H[i][1] , w = L[i];
		adj[v].push_back({u , w});
		adj[u].push_back({v , w});
	}
	DFS(0);
	return (ans == INF ? -1 : ans);
}

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