Submission #379931

#	Time	Username	Problem	Language	Result	Execution time	Memory
379931		AriaH	Mousetrap (CEOI17_mousetrap)	C++11	100 / 100	1940 ms	260744 KiB

mousetrap

/** I can do this all day **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

int n, root,  m, dp[N], cost[N], P[LOG][N], H[N];

vector < int > G[N];

int LCA(int v, int u)
{
	if(H[v] > H[u]) swap(u, v);
	int del = H[u] - H[v];
	for(int T = 0; T < LOG; T ++) if(del >> T & 1) u = P[T][u];
	if(v == u) return v;
	for(int T = LOG - 1; ~T; T --)
	{
		if(P[T][v] ^ P[T][u])
		{
			u = P[T][u];
			v = P[T][v];
		}
	}
	return P[0][v];
}

void pre(int v)
{
	if(v ^ root)
	{
		cost[v] = cost[P[0][v]] + SZ(G[v]) - 1;
	}
	H[v] = H[P[0][v]] + 1;
	for(int T = 1; T < LOG; T ++) P[T][v] = P[T - 1][P[T - 1][v]];
	for(auto u : G[v])
	{
		if(u == P[0][v]) continue;
		P[0][u] = v;
		pre(u);
	}
}

void dfs(int v)
{
	if(v == root)
	{
		cost[v] = 0;
	}
	else
	{
		cost[v] = cost[v] - H[LCA(v, m)] + 1;
		if(LCA(v, m) == m) cost[v] ++;
	}
	int Mx1 = cost[v], Mx2 = cost[v], cnt = 0;
	for(auto u : G[v])
	{
		if(u == P[0][v]) continue;
		dfs(u);
		cnt ++;
		if(dp[u] > Mx1)
		{
			Mx2 = Mx1;
			Mx1 = dp[u];
		}
		else
		{
			Mx2 = max(Mx2, dp[u]);
		}
	}
	if(v == root)
	{
		dp[v] = 0;
		return;
	}
	if(cnt <= 1)
	{
		dp[v] = cost[v];
	}
	else
	{
		dp[v] = Mx2;
	}
}

bool check(int x)
{
	if(x < 0) return 0;
	int s = 1, node = m, bads = 0;
	for(auto u : G[node])
	{
		if(u == P[0][node]) continue;
		if(dp[u] > x)
		{
		    bads ++;
		}
	}
	s -= bads;
	x -= bads;
	if(s < 0 || x < 0) return 0;
	int last = m;
	node = P[0][node];
	s ++;
	while(node ^ root)
	{
		bads = 0;
		for(auto u : G[node])
		{
			if(u == last || u == P[0][node]) continue;
			if(dp[u] > x)
			{
			    bads ++;
			}
		}
		s -= bads;
		x -= bads;
		if(x < 0 || s < 0) return 0;
		last = node;
		node = P[0][node];
		s ++;
	}
	return 1;
}

int main()
{
	scanf("%d%d%d", &n, &root, &m);
	if(root == m) return !printf("0");
	for(int i = 1; i < n; i ++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	pre(root);
	dfs(root);
	/*for(int i = 1; i <= n; i ++)
	{
		printf("i = %d cost : %d dp : %d\n", i, cost[i], dp[i]);
	}
	*/
	int d = -1, up = n + 10;
	while(up - d > 1)
	{
		int mid = (up + d) >> 1;
		if(check(mid))
		{
			up = mid;
		}
		else
		{
			d = mid;
		}
	}
	printf("%d", up);
	return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message (stderr)

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:147:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  147 |  scanf("%d%d%d", &n, &root, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  152 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 20 / 20
• Subtask 4: 35 / 35