Submission #40977534

---

Source Code Expand

#include <bits/stdc++.h>
namespace // to fold that junk code
{
#define filein(x) freopen(x".in", "r", stdin);
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout);
#define files(x) freopen(x".in", "r", stdin), freopen(x".ans", "w", stdout);
using namespace std;
#define cT const T&
template<typename T>
inline T chkmin(T& x, cT y){if (x > y) x = y; return x;}
template<typename T>
inline T chkmax(T& x, cT y){if (x < y) x = y; return x;}
template <typename T>
inline bool inrange(cT x, cT l, cT r){return (l <= x) && (x <= r);}
template <typename T>
inline bool inrange(cT l, cT r, cT L, cT R){return (L <= l) && (r <= R);}
#undef cT
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef unsigned u32;
template <typename T>
using pr = pair<T, T>;
typedef pr<int> pii;
typedef pr<ll> pll;
typedef pr<db> pdd;
typedef complex<double> cp;
typedef vector<int> vi;
inline void YN(bool x){puts(x ? "Yes" : "No");}
}
const int N = 222222, INF = 0x3f3f3f3f;
int n, dp[N][3];
vector<int> g[N];
inline void addedge(int u, int v){g[u].emplace_back(v);}
inline void ade(int u, int v){addedge(u, v); addedge(v, u);}
void dfs(int u, int fa, int lim)
{
	dp[u][0] = dp[u][1] = dp[u][2] = 0;
	for (int v : g[u])
	{
		if (v == fa) continue;
		dfs(v, u, lim);
		int a = INF, b = INF, c = INF;
		if (dp[u][0] + dp[v][1]     <= lim) chkmin(b, max(dp[u][0], dp[v][1]));
		if (dp[u][0] + dp[v][2] + 1 <= lim) chkmin(a, max(dp[u][0], dp[v][2] + 1));
		if (dp[u][1] + dp[v][1]     <= lim) chkmin(c, max(dp[u][1], dp[v][1]));
		if (dp[u][1] + dp[v][2] + 1 <= lim) chkmin(b, max(dp[u][1], dp[v][2] + 1));
		if (dp[u][2] + dp[v][2] + 1 <= lim) chkmin(c, max(dp[u][2], dp[v][2] + 1));
		dp[u][0] = a; dp[u][1] = min(b, dp[u][0]); dp[u][2] = min(c, dp[u][1]);
	}
}
int main()
{
#ifndef ONLINE_JUDGE
	filein("i");
#endif
	scanf("%d", &n);
	for (int i=1, u, v; i<n; i++){scanf("%d%d", &u, &v); ade(u, v);}
	int l = 0, r = __lg(n) + 10;
	while (l <= r)
	{
		int mid = (l + r) >> 1; dfs(1, 0, mid);
		if (dp[1][2] < INF) r = mid - 1;
		else l = mid + 1;
	}
	printf("%d\n", l + 1);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:58:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   58 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
./Main.cpp:59:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   59 |  for (int i=1, u, v; i<n; i++){scanf("%d%d", &u, &v); ade(u, v);}
      |                                ~~~~~^~~~~~~~~~~~~~~~

Judge Result