Submission #686480

#	Time	Username	Problem	Language	Result	Execution time	Memory
686480		pragmatist	Race (IOI11_race)	C++17	100 / 100	449 ms	84444 KiB

race

#include "race.h"
#include<bits/stdc++.h>
 
#define sz(v) (int)v.size()
#define ll long long
#define pb push_back
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define nl "\n"

using namespace std;
using pii = pair<int, int>;

const int N = (int)2e5 + 7; // make sure this is right
const int inf = (int)1e9;
const ll INF = (ll)3e18 + 7; 
const ll MOD = (ll)1e9 + 7; // make sure this is right

pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int n, k, d[N], ans = inf;
vector<pii> g[N];
map<ll, int> mn[N];

int comb(map<ll, int> &a, map<ll, int> &b, int q, ll w) {
	int res = inf;
	if(sz(a) < sz(b)) {
		for(auto [x, y] : a) {
			if(b.count(k + 2 * w - x)) {
				res = min(res, y + b[k + 2 * w - x] - 2 * q);
			}
		}
		for(auto [x, y] : a) {
			if(!b.count(x)) {
				b[x] = y;
			} else b[x] = min(b[x], y);
		}
		a.swap(b);
		b.clear();				
	} else {
		for(auto [x, y] : b) {
			if(a.count(k + 2 * w - x)) {
				res = min(res, y + a[k + 2 * w - x] - 2 * q);
			}
		}
		for(auto [x, y] : b) {
			if(!a.count(x)) a[x] = y;
			else a[x] = min(a[x], y);
		}  
	}
	return res;
} 
       
void dfs(int v, int pr, ll len) {
	for(auto [to, w] : g[v]) {
		if(to == pr) continue;
		d[to] = d[v] + 1;
		dfs(to, v, len + w);  
	}	
	for(auto [to, w] : g[v]) {
		ans = min(ans, comb(mn[v], mn[to], d[v], len));
	}
	mn[v][len] = d[v];
	if(mn[v].count(len + k)) {
		ans = min(ans, mn[v][len + k] - d[v]);
	}
}

int best_path(int n_, int k_, int h_[][2], int l_[]) {
	n = n_;
	k = k_;
	for(int i = 0; i < n - 1; ++i) {
		h_[i][0]++;
		h_[i][1]++;
		g[h_[i][0]].pb({h_[i][1], l_[i]});
		g[h_[i][1]].pb({h_[i][0], l_[i]});
	}
	dfs(1, 1, 0);
	return (ans == inf ? -1 : ans);
}

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