Submission #118085

#	Time	Username	Problem	Language	Result	Execution time	Memory
118085		MAMBA	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
#ifndef LOCAL
#include "grader.h"
#endif

using namespace std;

inline void fileIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

inline void read() {}
template <class S>
inline void read(S &arg) {
	cin >> arg;
}
template <class S>
inline void readA(S Lptr, S Rptr) {
	while (Lptr != Rptr) {
		read(*Lptr);
		Lptr++;
	}
}
template <class S, class... T>
inline void read(S &arg, T &... rest) {
	read(arg);
	read(rest...);
}

inline void write() {}
template <class S>
inline void write(S arg) {
	cout << arg;
}
template <class S>
inline void writeA(S Lptr, S Rptr, char del = ' ') {
	if (Lptr != Rptr) {
		write(*Lptr);
		Lptr++;
	}
	while (Lptr != Rptr) {
		write(del);
		write(*Lptr);
		Lptr++;
	}
}
template <class S, class... T>
inline void write(S arg, T... rest) {
	write(arg);
	write(' ');
	write(rest...);
}

#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(), x.end()

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

template <class T, class S>
inline bool smin(T &a, S b) {
	return (T)b < a ? a = b, 1 : 0;
}
template <class T, class S>
inline bool smax(T &a, S b) {
	return a < (T)b ? a = b, 1 : 0;
}

constexpr int MOD = 1e9 + 7;
constexpr int N = 2e5 + 10;

template <typename T>
inline T mod(T &v) {
	return v = (v % MOD + MOD) % MOD;
}
template <typename S, typename T>
inline S add(S &l, T r) {
	return mod(l += r);
}

ll po(ll v, ll u) {
	return u ? po(v * v % MOD, u >> 1) * (u & 1 ? v : 1) % MOD : 1;
}


int H[N][2], L[N], sz[N];
int ans = 1e9, k;
vi adj[N];
int vec[N];

bitset<N> alive;
int mp[(int)1e6 + 10];

void predfs(int v, int par = -1) {
	sz[v] = 1;
	for (auto e : adj[v]) {
		int u = H[e][0] ^ H[e][1] ^ v;
		if (alive[u] && u ^ par) {
			predfs(u , v);
			sz[v] += sz[e];
		}
	}
}

int cent(int v, int s = -1,int par = -1) {
	if (s == -1) s = sz[v];
	int mx = s - sz[v];
	for (auto e : adj[v]) {
		int u = H[e][0] ^ H[e][1] ^ v;
		if (alive[u] && u ^ par) {
			smax(mx , sz[u]);
			int local = cent(u , s , v);
			if (~local) return local;
		}
	}
	if (mx <= (s / 2)) return v;
	return -1;
}

void dfs1(int v, int par, int dist, int dist2 = 1) {
	if (dist > k) return;
	if (~mp[k - dist]) smin(ans , mp[k - dist] + dist2);
   	for (auto e : adj[v]) {
		int u = H[e][0] ^ H[e][1] ^ v;
		if (alive[u] && u ^ par)
			dfs1(u , v , dist + L[e] , dist2 + 1);
	}
}
void dfs2(int v, int par, int dist, int dist2 = 1) {
	if (dist > k) return;
	if (~mp[dist]) smin(mp[dist]  , dist2);
	else {
	   	mp[dist] = dist2;
		vec[R++] = dist;
	}
   	for (auto e : adj[v]) {
		int u = H[e][0] ^ H[e][1] ^ v;
		if (alive[u] && u ^ par)
			dfs2(u , v , dist + L[e] , dist2 + 1);
	}
}

void solve(int v) {
	predfs(v);
	alive[v = cent(v)] = false;
	auto f = [v]() {
		reverse(all(adj[v]));
		for (auto e : adj[v]) {
			int u = H[e][0] ^ H[e][1] ^ v;
			if (alive[u]) {
				dfs1(u, v, L[e]);
				dfs2(u, v, L[e]);
			}
		}
		if (~mp[k]) smin(ans , mp[k]);
		rep(i , 0 , R) mp[vec[i]] = -1;
		R = 0;
	};
	f();
	f();
	for (auto e : adj[v]) {
		int u = H[e][0] ^ H[e][1] ^ v;
		if (alive[u]) solve(u);
	}
}

int best_path(int n, int k2, int H2[][2],  int L2[]) {
	memset(mp , -1, sizeof(mp));
	k = k2;
	rep(i , 0 , n - 1) {
		H[i][0] = H2[i][0];
		H[i][1] = H2[i][1];
		L[i] = L2[i];
		adj[H[i][0]].pb(i);
		adj[H[i][1]].pb(i);
	}

	alive.set();

	solve(0);

	if (ans > n) ans = -1;
	return ans;

}

Compilation message (stderr)

race.cpp:3:10: fatal error: grader.h: No such file or directory
 #include "grader.h"
          ^~~~~~~~~~
compilation terminated.