제출 #753824

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
753824		MetalPower	Race (IOI11_race)	C++14	100 / 100	441 ms	108036 KiB

race

#include "race.h"

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

#define ll long long
#define pii pair<int, int>
#define fi first
#define se second

const int MX = 2e5 + 10;
const int INF = 1e9;

int _K, off[MX], ans = INF; ll dep[MX];
map<ll, int>* dp[MX];
vector<pii> adj[MX];

void ae(int u, int v, int w){
	adj[u].push_back({v, w});
	adj[v].push_back({u, w});
}

void chmin(int& a, int b){
	if(b < a) a = b;
}

void add(int u, int v, int cdep){ // add dp of v to dp of u
	if(dp[u] -> size() < dp[v] -> size()) swap(dp[u], dp[v]), swap(off[u], off[v]);
	for(pii x : (*dp[v])){
		int len = _K + 2 * cdep - x.fi;
		if(dp[u] -> count(len)) chmin(ans, x.se + off[v] + (*dp[u])[len] + off[u]);
	}
	for(pii x : (*dp[v])){
		if(dp[u] -> count(x.fi)) chmin((*dp[u])[x.fi], x.se + off[v] - off[u]);
		else (*dp[u])[x.fi] = x.se + off[v] - off[u];
	}
}

void dfs(int u, int v){

	dp[u] = new map<ll, int>();
	(*dp[u])[dep[u]] = 0;
	off[u] = 0;

	for(pii nxt : adj[u]){
		if(nxt.fi == v) continue;
		dep[nxt.fi] = dep[u] + nxt.se;
		dfs(nxt.fi, u);
		off[nxt.fi]++;
		add(u, nxt.fi, dep[u]);
	}
}

int best_path(int N, int K, int H[][2], int L[]){
	_K = K;
	for(int i = 0; i < N - 1; i++) ae(H[i][0], H[i][1], L[i]);
	dfs(0, -1);
	if(ans != INF) return ans; 
	else return -1;
}

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