제출 #349980

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
349980		NachoLibre	경주 (Race) (IOI11_race)	C++14	100 / 100	482 ms	81516 KiB

race

#include <bits/stdc++.h>
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("-O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("-Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("unroll-loops")
using namespace std;
#ifndef wambule
#include "race.h"
#endif

inline void minfp(int);
long long gk;

struct vyv {
	long long x;
	int y;
	map<long long, int> ma;
	vyv() {
		x = y = 0;
		ma.clear();
	}

	void clc(long long a, int b) {
		a -= x;
		b -= y;
		long long k = gk - x * 2;
		if(ma.find(k - a) != ma.end()) {
			minfp(ma[k - a] + y + b + y);
		}
	}

	void add(long long a, int b) {
		a -= x;
		b -= y;
		if(ma.find(a) == ma.end()) {
			ma[a] = b;
		} else {
			ma[a] = min(ma[a], b);
		}
	}

	void adc(long long a, int b) {
		clc(a, b);
		add(a, b);
	}

	void lft(int a, int b) {
		x += a;
		y += b;
	}
};

const int N = 200005, K = 1000006;
int fp = -1, qz[N], ms[N], mw[N];
vector<pair<int, int>> v[N];

inline void minfp(int x) {
	fp = (fp ^ -1 && fp < x ? fp : x);
}

void ovo(int dg = 0, int op = -1, vyv &a = *new vyv()) {
	// cout << "[jent] " << dg << "\n";
	if(!(op ^ -1 && v[dg].size() == 1)) {
		ovo(ms[dg], dg, a);
		a.lft(mw[dg], 1);
	}
	a.adc(0, 0);
	for(auto p : v[dg]) {
		if(p.first ^ op && p.first ^ ms[dg]) {
			vyv x;
			ovo(p.first, dg, x);
			x.lft(p.second, 1);
			for(auto it = x.ma.begin(); it != x.ma.end(); ++it) {
				a.clc(it->first + x.x, it->second + x.y);
			}
			for(auto it = x.ma.begin(); it != x.ma.end(); ++it) {
				a.add(it->first + x.x, it->second + x.y);
			}
		}
	}
	// cout << "[cont] " << dg << " " << "\n[^^^^] ";
	// for(auto it = a.ma.begin(); it != a.ma.end(); ++it) {
	// 	cout << "{" << it->first + a.x << ", " << it->second + a.y << "} ";
	// }
	// cout << "\n";
}

void omo(int dg = 0, int op = -1) {
	// cout << "[plze] " << dg << "\n";
	int mz = 0;
	for(auto p : v[dg]) {
		if(p.first ^ op) {
			omo(p.first, dg);
			qz[dg] += qz[p.first];
			if(qz[p.first] > mz) {
				mz = qz[p.first];
				ms[dg] = p.first;
				mw[dg] = p.second;
			}
		}
	}
}

int best_path(int n, int k, int h[][2], int l[]) {
	gk = k;
	for(int i = 0; i < n; ++i) {
		qz[i] = 1;
		v[i].clear();
	}
	for(int i = 0; i < n - 1; ++i) {
		v[h[i][0]].push_back({h[i][1], l[i]});
		v[h[i][1]].push_back({h[i][0], l[i]});
	}
	omo();
	ovo();
	return fp;
}

#ifdef wambule
mt19937_64 rnd(time(0));

long long R(long long l, long long r) {
	return 1ll * rnd() % (r - l + 1) + l;
}

long long Sr(long long r) {
	return R(0, r - 1);
}

void G(int n, int h[][2]) {
	vector<int> v;
	for(int i = 0; i < n; ++i) {
		v.push_back(i);
	}
	random_shuffle(v.begin(), v.end());
	for(int i = 0; i < n - 1; ++i) {
		h[i][0] = v[R(0, i)];
		h[i][1] = v[i + 1];
	}
}

int h[N][2];
int l[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	srand(time(0));
	// cin.get();
	////
	int n = 4;
	int k = 3;
	int h[][2] = {0, 1, 1, 2, 1, 3};
	int l[]    = {1, 2, 4};
	////
	// int n = 11;
	// int k = 12;
	// int h[][2] = {0, 1, 0, 2, 2, 3, 3, 4, 4, 5, 0, 6, 6, 7, 6, 8, 8, 9, 8, 10};
	// int l[]    = {3, 4, 5, 4, 6, 3, 2, 5, 6, 7};
	////
	// int n = 200000;
	// int k = 1000000;
	// G(n, h);
	// for(int i = 0; i < n - 1; ++i) {
	// 	l[i] = R(0, 1000000);
	// }
	////
	int rtnd = best_path(n, k, h, l);
	cout << "[fnps] " << rtnd << endl;
	cin.get();
	return 0;
}
#endif

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