Submission #237120

#	Time	Username	Problem	Language	Result	Execution time	Memory
237120		mode149256	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

/*input

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

namespace my_template {
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}
}
using namespace my_template;

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 200101;
const int DID = 1e6;

vb buvau(MX, false);
queue<int> toliau;
vi sz(MX);
int piv;
vi edges[MX];
vi len[MX];
int ats = MOD;

vpi pir(DID + 1, {MOD, -1});
vpi ant(DID + 1, {MOD, -1});

unordered_set<int> visi;

int update(int x, int p) {
	piv++;
	sz[x] = 1;

	for (auto u : edges[x])
		if (!buvau[u] and u != p)
			sz[x] += update(u, x);

	return sz[x];
}

void prid(int x, int p, int curr, int cnt, int origin) {
	if (curr <= reik) {
		visi.insert(curr);
		if (pir[curr].y == origin) {
			pir[curr].x = min(pir[curr].x, cnt);
		} else if (ant[curr].y == origin) {
			ant[curr].x = min(ant[curr].x, cnt);
			if (ant[curr] < pir[curr])
				swap(pir[curr], ant[curr]);
		} else {
			if (cnt <= pir[curr].x) {
				ant[curr] = pir[curr];
				pir[curr] = {cnt, origin};
			} else if (cnt < ant[curr].x) {
				ant[curr] = {cnt, origin};
			}
		}
	}

	for (int i = 0; i < (int)edges[x].size(); ++i)
	{
		int u = edges[x][i];
		if (!buvau[u] and u != p)
			prid(u, x, curr + len[x][i], cnt + 1, origin);
	}
}

int reik;

void proccess(int x) {
	visi.clear();
	for (int i = 0; i < (int)edges[x].size(); ++i)
	{
		int u = edges[x][i];
		if (!buvau[u])
			prid(u, x, len[x][i], 1, u);
	}

	for (auto u : visi) {
		if (u > reik) continue;
		if (pir[u].y == -1 or pir[reik - u].y == -1) continue;

		if (pir[u].y != pir[reik - u].y) {
			// printf("u = %d, kit = %d, pir pir %d %d\n", u, reik - u, pir[u].x, pir[reik - u].x);
			ats = min(ats, pir[u].x + pir[reik - u].x);
		} else if (ant[reik - u].y != -1 and pir[u].y != ant[reik - u].y) {
			// printf("u = %d, kit = %d, pir ant %d %d\n", u, reik - u, pir[u].x, ant[reik - u].x);
			ats = min(ats, pir[u].x + ant[reik - u].x);
		} else if (ant[u].y != -1 and ant[u].y != pir[reik - u].y) {
			// printf("u = %d, kit = %d, ant pir %d %d\n", u, reik - u, ant[u].x, pir[reik - u].x);
			ats = min(ats, ant[u].x + pir[reik - u].x);
		}
		//  else if (ant[u].y != -1 and ant[reik - u].y != -1 and ant[u].y != ant[reik - u].y) {
		// 	ats = min(ats, ant[u].x + ant[reik - u].x);
		// }
	}

	for (auto u : visi) {
		pir[u] = ant[u] = {MOD, -1};
	}

	// for (int i = 0; i < (int)edges[x].size(); ++i)
	// {
	// 	int u = edges[x][i];
	// 	if (!buvau[u])
	// 		prid(u, x, len[x][i], -1, u);
	// }
}

void centroid(int x, int p, int dydis) {
	for (auto u : edges[x]) {
		if (!buvau[u] and u != p and sz[u] > dydis / 2) {
			centroid(u, x, dydis);
			return;
		}
	}

	// x is centroid
	proccess(x);
	buvau[x] = true;

	for (auto u : edges[x])
		if (!buvau[u])
			toliau.push(u);
}

int best_path(int N, int K, int H[][2], int L[])
{
	for (int i = 0; i < N - 1; ++i)
	{
		edges[H[i][0]].emplace_back(H[i][1]);
		len[H[i][0]].emplace_back(L[i]);
		edges[H[i][1]].emplace_back(H[i][0]);
		len[H[i][1]].emplace_back(L[i]);
	}

	pir[0] = {0, -5};
	reik = K;
	toliau.push(0);
	while (toliau.size()) {
		int c = toliau.front(); toliau.pop();

		piv = 0;
		update(c, -1);
		centroid(c, -1, piv);
	}

	if (ats == MOD) return -1;
	else return ats;
}

Compilation message (stderr)

race.cpp: In function 'void prid(int, int, int, int, int)':
race.cpp:87:14: error: 'reik' was not declared in this scope
  if (curr <= reik) {
              ^~~~
race.cpp:87:14: note: suggested alternative: 'ceil'
  if (curr <= reik) {
              ^~~~
              ceil