oj.uz

Submission #65995

# Submission time Handle Problem Language Result Execution time Memory
65995 2018-08-09T09:46:54 Z polyfish Mousetrap (CEOI17_mousetrap) C++14
100 / 100
 1845 ms 219008 KB 
//I love armpit fetish

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 1000002;
const int INF = 1e9;

int n, root, mouse_vertice, f[MAX_N], par[MAX_N];
bool on_path[MAX_N];
vector<int> p, g[MAX_N];

void enter() {
	cin >> n >> root >> mouse_vertice;
	for (int i=1; i<n; ++i) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}	
}

void fix_root(int u) {
	for (int i=0; i<g[u].size(); ++i) {
		int v = g[u][i];
		if (v!=par[u]) {
			par[v] = u;
			fix_root(v);
		}
	}
}

bool find_path(int u, int fn) {
	if (u==fn)
		return on_path[u] = true;
	for (int i=0; i<g[u].size(); ++i) {
		int v = g[u][i];
		if (v!=par[u] && find_path(v, fn))
			return on_path[u] = true;
	}
	return false;
}

int dp(int u) {
	int m1 = 0, m2 = 0;
	for (int i=0; i<g[u].size(); ++i) {
		int v = g[u][i];
		if (v!=par[u]) {
			int tmp = dp(v);
			if (tmp>=m1) {
				m2 = m1;
				m1 = tmp;
			}
			else {
				m2 = max(m2, tmp);
			}
		}
	}
	return f[u] = g[u].size() - 1 + m2;
}

void init_tree() {
	fix_root(root);
	find_path(root, mouse_vertice);
	dp(root);
}

bool check(int x) {
	int used = 0, remain = 0;
	int cur = mouse_vertice;
	int sum_deg = 0;
	for (int i=1; i<=n; ++i)
		if (i!=root && on_path[i])
			sum_deg += (g[i].size() - 2);
	while (cur!=root) {
		sum_deg -= (g[cur].size() - 2);
		++remain;
		p.clear();
		for (int i=0; i<g[cur].size(); ++i) {
			int u = g[cur][i];
			if (!on_path[u])
				p.push_back(f[u]);
		}
		sort(p.begin(), p.end(), greater<int>());
		if (p.size()>remain && 
			p[remain] + g[cur].size() - 2 + (cur==mouse_vertice) + sum_deg + used > x) {
			//debug(used);
			//debug(cur);
			return false;
		}
		int tmp = 0;
		for (int i=0; i<p.size(); ++i) {
			if (p[i] + g[cur].size() - 2 + (cur==mouse_vertice) + sum_deg + used > x) {
				--remain;
				//debug(p[i] + g[cur].size() - 2 + (cur==mouse_vertice) + sum_deg + used);
				++tmp;
			}
		}
		used += tmp;
		cur = par[cur];
	}
	return used <= x;
}

int bisect() {
	int l = 0, r = INF, mid = (l + r) / 2;
	while (l!=mid && mid!=r) {
		if (check(mid))
			r = mid;
		else
			l = mid;
		mid = (l + r) / 2;
	}
	for (int i=l; i<=r; ++i)
		if (check(i))
			return i;
	assert(0);
}

int main() {
	//#define OFFLINE_JUDGE doraemon
	#ifdef OFFLINE_JUDGE
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	enter();
	init_tree();
	//PR(f, n);
	//debug(check(1));
	cout << bisect();
}

Compilation message

mousetrap.cpp: In function 'void fix_root(int)':
mousetrap.cpp:30:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<g[u].size(); ++i) {
                ~^~~~~~~~~~~~
mousetrap.cpp: In function 'bool find_path(int, int)':
mousetrap.cpp:42:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<g[u].size(); ++i) {
                ~^~~~~~~~~~~~
mousetrap.cpp: In function 'int dp(int)':
mousetrap.cpp:52:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<g[u].size(); ++i) {
                ~^~~~~~~~~~~~
mousetrap.cpp: In function 'bool check(int)':
mousetrap.cpp:85:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<g[cur].size(); ++i) {
                 ~^~~~~~~~~~~~~~
mousetrap.cpp:91:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (p.size()>remain && 
       ~~~~~~~~^~~~~~~
mousetrap.cpp:92:74: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    p[remain] + g[cur].size() - 2 + (cur==mouse_vertice) + sum_deg + used > x) {
mousetrap.cpp:98:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<p.size(); ++i) {
                 ~^~~~~~~~~
mousetrap.cpp:99:73: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (p[i] + g[cur].size() - 2 + (cur==mouse_vertice) + sum_deg + used > x) {

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 22 ms 23932 KB Output is correct
3 Correct 30 ms 23932 KB Output is correct
4 Correct 25 ms 24100 KB Output is correct
5 Correct 23 ms 24100 KB Output is correct
6 Correct 23 ms 24116 KB Output is correct
7 Correct 27 ms 24164 KB Output is correct
8 Correct 25 ms 24168 KB Output is correct
9 Correct 23 ms 24168 KB Output is correct
10 Correct 26 ms 24168 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 531 ms 63332 KB Output is correct
2 Correct 467 ms 63332 KB Output is correct
3 Correct 1337 ms 64396 KB Output is correct
4 Correct 655 ms 64396 KB Output is correct
5 Correct 1739 ms 64592 KB Output is correct
6 Correct 1456 ms 64592 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 22 ms 23932 KB Output is correct
3 Correct 30 ms 23932 KB Output is correct
4 Correct 25 ms 24100 KB Output is correct
5 Correct 23 ms 24100 KB Output is correct
6 Correct 23 ms 24116 KB Output is correct
7 Correct 27 ms 24164 KB Output is correct
8 Correct 25 ms 24168 KB Output is correct
9 Correct 23 ms 24168 KB Output is correct
10 Correct 26 ms 24168 KB Output is correct
11 Correct 24 ms 64592 KB Output is correct
12 Correct 30 ms 64592 KB Output is correct
13 Correct 25 ms 64592 KB Output is correct
14 Correct 27 ms 64592 KB Output is correct
15 Correct 32 ms 64592 KB Output is correct
16 Correct 29 ms 64592 KB Output is correct
17 Correct 29 ms 64592 KB Output is correct
18 Correct 26 ms 64592 KB Output is correct
19 Correct 25 ms 64592 KB Output is correct
20 Correct 26 ms 64592 KB Output is correct
21 Correct 33 ms 64592 KB Output is correct
22 Correct 27 ms 64592 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 22 ms 23932 KB Output is correct
3 Correct 30 ms 23932 KB Output is correct
4 Correct 25 ms 24100 KB Output is correct
5 Correct 23 ms 24100 KB Output is correct
6 Correct 23 ms 24116 KB Output is correct
7 Correct 27 ms 24164 KB Output is correct
8 Correct 25 ms 24168 KB Output is correct
9 Correct 23 ms 24168 KB Output is correct
10 Correct 26 ms 24168 KB Output is correct
11 Correct 531 ms 63332 KB Output is correct
12 Correct 467 ms 63332 KB Output is correct
13 Correct 1337 ms 64396 KB Output is correct
14 Correct 655 ms 64396 KB Output is correct
15 Correct 1739 ms 64592 KB Output is correct
16 Correct 1456 ms 64592 KB Output is correct
17 Correct 24 ms 64592 KB Output is correct
18 Correct 30 ms 64592 KB Output is correct
19 Correct 25 ms 64592 KB Output is correct
20 Correct 27 ms 64592 KB Output is correct
21 Correct 32 ms 64592 KB Output is correct
22 Correct 29 ms 64592 KB Output is correct
23 Correct 29 ms 64592 KB Output is correct
24 Correct 26 ms 64592 KB Output is correct
25 Correct 25 ms 64592 KB Output is correct
26 Correct 26 ms 64592 KB Output is correct
27 Correct 33 ms 64592 KB Output is correct
28 Correct 27 ms 64592 KB Output is correct
29 Correct 28 ms 64592 KB Output is correct
30 Correct 671 ms 76884 KB Output is correct
31 Correct 547 ms 90432 KB Output is correct
32 Correct 1084 ms 151660 KB Output is correct
33 Correct 577 ms 164156 KB Output is correct
34 Correct 1654 ms 164156 KB Output is correct
35 Correct 1696 ms 164156 KB Output is correct
36 Correct 1833 ms 164156 KB Output is correct
37 Correct 1845 ms 176004 KB Output is correct
38 Correct 1222 ms 192072 KB Output is correct
39 Correct 1218 ms 205488 KB Output is correct
40 Correct 1339 ms 219008 KB Output is correct