oj.uz

Submission #118087

# Submission time Handle Problem Language Result Execution time Memory
118087 2019-06-18T07:02:31 Z MAMBA Race (IOI11_race) C++17
21 / 100
 3000 ms 16344 KB 
#include <bits/stdc++.h>
#ifndef LOCAL
#include "race.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], R;

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;

}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9088 KB Output is correct
2 Correct 9 ms 9088 KB Output is correct
3 Correct 10 ms 9088 KB Output is correct
4 Correct 9 ms 8960 KB Output is correct
5 Correct 8 ms 8960 KB Output is correct
6 Correct 9 ms 8960 KB Output is correct
7 Correct 9 ms 8960 KB Output is correct
8 Correct 9 ms 8960 KB Output is correct
9 Correct 9 ms 8960 KB Output is correct
10 Correct 10 ms 8960 KB Output is correct
11 Correct 9 ms 8960 KB Output is correct
12 Correct 9 ms 8960 KB Output is correct
13 Correct 9 ms 8960 KB Output is correct
14 Correct 9 ms 9088 KB Output is correct
15 Correct 9 ms 8960 KB Output is correct
16 Correct 10 ms 9088 KB Output is correct
17 Correct 9 ms 9088 KB Output is correct
18 Correct 10 ms 9088 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9088 KB Output is correct
2 Correct 9 ms 9088 KB Output is correct
3 Correct 10 ms 9088 KB Output is correct
4 Correct 9 ms 8960 KB Output is correct
5 Correct 8 ms 8960 KB Output is correct
6 Correct 9 ms 8960 KB Output is correct
7 Correct 9 ms 8960 KB Output is correct
8 Correct 9 ms 8960 KB Output is correct
9 Correct 9 ms 8960 KB Output is correct
10 Correct 10 ms 8960 KB Output is correct
11 Correct 9 ms 8960 KB Output is correct
12 Correct 9 ms 8960 KB Output is correct
13 Correct 9 ms 8960 KB Output is correct
14 Correct 9 ms 9088 KB Output is correct
15 Correct 9 ms 8960 KB Output is correct
16 Correct 10 ms 9088 KB Output is correct
17 Correct 9 ms 9088 KB Output is correct
18 Correct 10 ms 9088 KB Output is correct
19 Correct 9 ms 8960 KB Output is correct
20 Correct 10 ms 8960 KB Output is correct
21 Correct 18 ms 9088 KB Output is correct
22 Correct 13 ms 9088 KB Output is correct
23 Correct 13 ms 9088 KB Output is correct
24 Correct 37 ms 9096 KB Output is correct
25 Correct 21 ms 9088 KB Output is correct
26 Correct 12 ms 9088 KB Output is correct
27 Correct 12 ms 9088 KB Output is correct
28 Correct 15 ms 9088 KB Output is correct
29 Correct 17 ms 9088 KB Output is correct
30 Correct 24 ms 9088 KB Output is correct
31 Correct 21 ms 9088 KB Output is correct
32 Correct 22 ms 9088 KB Output is correct
33 Correct 26 ms 9088 KB Output is correct
34 Correct 15 ms 9088 KB Output is correct
35 Correct 16 ms 9088 KB Output is correct
36 Correct 15 ms 9088 KB Output is correct
37 Correct 29 ms 9060 KB Output is correct
38 Correct 21 ms 9088 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9088 KB Output is correct
2 Correct 9 ms 9088 KB Output is correct
3 Correct 10 ms 9088 KB Output is correct
4 Correct 9 ms 8960 KB Output is correct
5 Correct 8 ms 8960 KB Output is correct
6 Correct 9 ms 8960 KB Output is correct
7 Correct 9 ms 8960 KB Output is correct
8 Correct 9 ms 8960 KB Output is correct
9 Correct 9 ms 8960 KB Output is correct
10 Correct 10 ms 8960 KB Output is correct
11 Correct 9 ms 8960 KB Output is correct
12 Correct 9 ms 8960 KB Output is correct
13 Correct 9 ms 8960 KB Output is correct
14 Correct 9 ms 9088 KB Output is correct
15 Correct 9 ms 8960 KB Output is correct
16 Correct 10 ms 9088 KB Output is correct
17 Correct 9 ms 9088 KB Output is correct
18 Correct 10 ms 9088 KB Output is correct
19 Execution timed out 3006 ms 16344 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9088 KB Output is correct
2 Correct 9 ms 9088 KB Output is correct
3 Correct 10 ms 9088 KB Output is correct
4 Correct 9 ms 8960 KB Output is correct
5 Correct 8 ms 8960 KB Output is correct
6 Correct 9 ms 8960 KB Output is correct
7 Correct 9 ms 8960 KB Output is correct
8 Correct 9 ms 8960 KB Output is correct
9 Correct 9 ms 8960 KB Output is correct
10 Correct 10 ms 8960 KB Output is correct
11 Correct 9 ms 8960 KB Output is correct
12 Correct 9 ms 8960 KB Output is correct
13 Correct 9 ms 8960 KB Output is correct
14 Correct 9 ms 9088 KB Output is correct
15 Correct 9 ms 8960 KB Output is correct
16 Correct 10 ms 9088 KB Output is correct
17 Correct 9 ms 9088 KB Output is correct
18 Correct 10 ms 9088 KB Output is correct
19 Correct 9 ms 8960 KB Output is correct
20 Correct 10 ms 8960 KB Output is correct
21 Correct 18 ms 9088 KB Output is correct
22 Correct 13 ms 9088 KB Output is correct
23 Correct 13 ms 9088 KB Output is correct
24 Correct 37 ms 9096 KB Output is correct
25 Correct 21 ms 9088 KB Output is correct
26 Correct 12 ms 9088 KB Output is correct
27 Correct 12 ms 9088 KB Output is correct
28 Correct 15 ms 9088 KB Output is correct
29 Correct 17 ms 9088 KB Output is correct
30 Correct 24 ms 9088 KB Output is correct
31 Correct 21 ms 9088 KB Output is correct
32 Correct 22 ms 9088 KB Output is correct
33 Correct 26 ms 9088 KB Output is correct
34 Correct 15 ms 9088 KB Output is correct
35 Correct 16 ms 9088 KB Output is correct
36 Correct 15 ms 9088 KB Output is correct
37 Correct 29 ms 9060 KB Output is correct
38 Correct 21 ms 9088 KB Output is correct
39 Execution timed out 3006 ms 16344 KB Time limit exceeded
40 Halted 0 ms 0 KB -