Submission #65995

#	Time	Username	Problem	Language	Result	Execution time	Memory
65995		polyfish	Mousetrap (CEOI17_mousetrap)	C++14	100 / 100	1845 ms	219008 KiB

mousetrap

//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 (stderr)

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 / 20
• Subtask 2: 25 / 25
• Subtask 3: 20 / 20
• Subtask 4: 35 / 35