oj.uz

답안 #118089

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
118089 2019-06-18T07:03:33 Z MAMBA 경주 (Race) (IOI11_race) C++17
100 / 100
 1470 ms 39536 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[u];
		}
	}
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 9088 KB Output is correct
2 Correct 9 ms 8960 KB Output is correct
3 Correct 8 ms 8960 KB Output is correct
4 Correct 8 ms 8960 KB Output is correct
5 Correct 9 ms 9088 KB Output is correct
6 Correct 9 ms 9060 KB Output is correct
7 Correct 8 ms 9088 KB Output is correct
8 Correct 9 ms 9088 KB Output is correct
9 Correct 8 ms 8960 KB Output is correct
10 Correct 9 ms 9088 KB Output is correct
11 Correct 9 ms 9088 KB Output is correct
12 Correct 8 ms 8960 KB Output is correct
13 Correct 9 ms 9088 KB Output is correct
14 Correct 9 ms 9088 KB Output is correct
15 Correct 8 ms 8960 KB Output is correct
16 Correct 9 ms 8960 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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 9088 KB Output is correct
2 Correct 9 ms 8960 KB Output is correct
3 Correct 8 ms 8960 KB Output is correct
4 Correct 8 ms 8960 KB Output is correct
5 Correct 9 ms 9088 KB Output is correct
6 Correct 9 ms 9060 KB Output is correct
7 Correct 8 ms 9088 KB Output is correct
8 Correct 9 ms 9088 KB Output is correct
9 Correct 8 ms 8960 KB Output is correct
10 Correct 9 ms 9088 KB Output is correct
11 Correct 9 ms 9088 KB Output is correct
12 Correct 8 ms 8960 KB Output is correct
13 Correct 9 ms 9088 KB Output is correct
14 Correct 9 ms 9088 KB Output is correct
15 Correct 8 ms 8960 KB Output is correct
16 Correct 9 ms 8960 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 9088 KB Output is correct
21 Correct 10 ms 9088 KB Output is correct
22 Correct 10 ms 9088 KB Output is correct
23 Correct 11 ms 9088 KB Output is correct
24 Correct 10 ms 9088 KB Output is correct
25 Correct 11 ms 9100 KB Output is correct
26 Correct 10 ms 9088 KB Output is correct
27 Correct 10 ms 9088 KB Output is correct
28 Correct 9 ms 9088 KB Output is correct
29 Correct 11 ms 9088 KB Output is correct
30 Correct 10 ms 9088 KB Output is correct
31 Correct 10 ms 9088 KB Output is correct
32 Correct 9 ms 9088 KB Output is correct
33 Correct 10 ms 9088 KB Output is correct
34 Correct 9 ms 9088 KB Output is correct
35 Correct 10 ms 9088 KB Output is correct
36 Correct 10 ms 9088 KB Output is correct
37 Correct 10 ms 9088 KB Output is correct
38 Correct 12 ms 8960 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 9088 KB Output is correct
2 Correct 9 ms 8960 KB Output is correct
3 Correct 8 ms 8960 KB Output is correct
4 Correct 8 ms 8960 KB Output is correct
5 Correct 9 ms 9088 KB Output is correct
6 Correct 9 ms 9060 KB Output is correct
7 Correct 8 ms 9088 KB Output is correct
8 Correct 9 ms 9088 KB Output is correct
9 Correct 8 ms 8960 KB Output is correct
10 Correct 9 ms 9088 KB Output is correct
11 Correct 9 ms 9088 KB Output is correct
12 Correct 8 ms 8960 KB Output is correct
13 Correct 9 ms 9088 KB Output is correct
14 Correct 9 ms 9088 KB Output is correct
15 Correct 8 ms 8960 KB Output is correct
16 Correct 9 ms 8960 KB Output is correct
17 Correct 9 ms 9088 KB Output is correct
18 Correct 10 ms 9088 KB Output is correct
19 Correct 443 ms 14956 KB Output is correct
20 Correct 340 ms 16376 KB Output is correct
21 Correct 387 ms 16376 KB Output is correct
22 Correct 344 ms 16376 KB Output is correct
23 Correct 145 ms 16376 KB Output is correct
24 Correct 105 ms 16596 KB Output is correct
25 Correct 307 ms 20500 KB Output is correct
26 Correct 175 ms 24304 KB Output is correct
27 Correct 347 ms 24396 KB Output is correct
28 Correct 566 ms 39536 KB Output is correct
29 Correct 640 ms 38460 KB Output is correct
30 Correct 325 ms 24336 KB Output is correct
31 Correct 331 ms 24420 KB Output is correct
32 Correct 395 ms 24448 KB Output is correct
33 Correct 469 ms 23896 KB Output is correct
34 Correct 432 ms 24696 KB Output is correct

Subtask #4
57.0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 9088 KB Output is correct
2 Correct 9 ms 8960 KB Output is correct
3 Correct 8 ms 8960 KB Output is correct
4 Correct 8 ms 8960 KB Output is correct
5 Correct 9 ms 9088 KB Output is correct
6 Correct 9 ms 9060 KB Output is correct
7 Correct 8 ms 9088 KB Output is correct
8 Correct 9 ms 9088 KB Output is correct
9 Correct 8 ms 8960 KB Output is correct
10 Correct 9 ms 9088 KB Output is correct
11 Correct 9 ms 9088 KB Output is correct
12 Correct 8 ms 8960 KB Output is correct
13 Correct 9 ms 9088 KB Output is correct
14 Correct 9 ms 9088 KB Output is correct
15 Correct 8 ms 8960 KB Output is correct
16 Correct 9 ms 8960 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 9088 KB Output is correct
21 Correct 10 ms 9088 KB Output is correct
22 Correct 10 ms 9088 KB Output is correct
23 Correct 11 ms 9088 KB Output is correct
24 Correct 10 ms 9088 KB Output is correct
25 Correct 11 ms 9100 KB Output is correct
26 Correct 10 ms 9088 KB Output is correct
27 Correct 10 ms 9088 KB Output is correct
28 Correct 9 ms 9088 KB Output is correct
29 Correct 11 ms 9088 KB Output is correct
30 Correct 10 ms 9088 KB Output is correct
31 Correct 10 ms 9088 KB Output is correct
32 Correct 9 ms 9088 KB Output is correct
33 Correct 10 ms 9088 KB Output is correct
34 Correct 9 ms 9088 KB Output is correct
35 Correct 10 ms 9088 KB Output is correct
36 Correct 10 ms 9088 KB Output is correct
37 Correct 10 ms 9088 KB Output is correct
38 Correct 12 ms 8960 KB Output is correct
39 Correct 443 ms 14956 KB Output is correct
40 Correct 340 ms 16376 KB Output is correct
41 Correct 387 ms 16376 KB Output is correct
42 Correct 344 ms 16376 KB Output is correct
43 Correct 145 ms 16376 KB Output is correct
44 Correct 105 ms 16596 KB Output is correct
45 Correct 307 ms 20500 KB Output is correct
46 Correct 175 ms 24304 KB Output is correct
47 Correct 347 ms 24396 KB Output is correct
48 Correct 566 ms 39536 KB Output is correct
49 Correct 640 ms 38460 KB Output is correct
50 Correct 325 ms 24336 KB Output is correct
51 Correct 331 ms 24420 KB Output is correct
52 Correct 395 ms 24448 KB Output is correct
53 Correct 469 ms 23896 KB Output is correct
54 Correct 432 ms 24696 KB Output is correct
55 Correct 29 ms 9816 KB Output is correct
56 Correct 27 ms 9728 KB Output is correct
57 Correct 143 ms 16376 KB Output is correct
58 Correct 48 ms 16312 KB Output is correct
59 Correct 173 ms 24376 KB Output is correct
60 Correct 1197 ms 39376 KB Output is correct
61 Correct 402 ms 24440 KB Output is correct
62 Correct 463 ms 24440 KB Output is correct
63 Correct 603 ms 24440 KB Output is correct
64 Correct 1470 ms 24788 KB Output is correct
65 Correct 478 ms 24952 KB Output is correct
66 Correct 824 ms 35832 KB Output is correct
67 Correct 199 ms 24940 KB Output is correct
68 Correct 582 ms 25500 KB Output is correct
69 Correct 591 ms 25476 KB Output is correct
70 Correct 580 ms 24672 KB Output is correct