Submission #551230

#	Time	Username	Problem	Language	Result	Execution time	Memory
551230		Keshi	Race (IOI11_race)	C++17	9 / 100	133 ms	36824 KiB

race

//In the name of God
#include "race.h"

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

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

const ll maxn = 2e5 + 100;
const ll mod = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()


int n, k, d[maxn];
ll s[maxn], s2[maxn];
vector<pii> g[maxn];
map<ll, ll> mn[maxn];
ll ans = INF;

void dfs(int v, int p = -1){
	mn[v][0] = 0;
	for(pii e : g[v]){
		int u = e.F;
		int c = e.S;
		if(u == p) continue;
		d[u] = d[v] + 1;
		dfs(u, v);
		s[u] += c;
		s2[u]++;
		if(Sz(mn[v]) < Sz(mn[u])){
			mn[v].swap(mn[u]);
			swap(s[v], s[u]);
			swap(s2[v], s2[u]);
		}
		for(pll i : mn[u]){
			i.F += s[u];
			i.S += s2[u];
			if(mn[v].find(i.F - s[v]) == mn[v].end()){
				mn[v][i.F - s[v]] = i.S - s2[v];
			}
			else mn[v][i.F - s[v]] = min(mn[v][i.F - s[v]], i.S - s2[v]);
			if(mn[v].find(k - i.F - s[v]) != mn[v].end()){
				ans = min(ans, i.S + mn[v][k - i.F - s[v]] + s2[v]);
			}
		}
	}
	return;
}

int best_path(int N, int K, int H[][2], int L[]){
	n = N;
	k = K;
	for(int i = 0; i < n - 1; i++){
		int v = H[i][0], u = H[i][1];
		g[v].pb(Mp(u, L[i]));
		g[u].pb(Mp(v, L[i]));
	}
	dfs(0);
	if(ans == INF) return -1;
	return ans;
}

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