oj.uz

Submission #705289

# Submission time Handle Problem Language Result Execution time Memory
705289 2023-03-03T20:09:18 Z badont Torrent (COI16_torrent) C++17
100 / 100
 698 ms 34340 KB 
#include<bits/stdc++.h>
using namespace std;

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif

using ll = long long;
using ld = long double;
using pii = pair<ll,ll>;

#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
	cout << "["; 
	for (auto it = v.begin(); it != v.end();) {
		cout << *it;
		if (++it != v.end()) cout << ", ";
	}
	return cout << "]";
}

//var 
ll T;

void solve() {
	ll n, a, b;
	cin >> n >> a >> b;
	a--; b--;

	vector e(n, vector<ll>());
	FOR (i, n - 1) {
		ll x, y;
		cin >> x >> y;
		x--; y--;
		e[x].pb(y);
		e[y].pb(x);
	}

	vector<ll> par(n);
	auto dfs_par = [&](auto dfs_par, ll g, ll p) -> void {
		par[g] = p;
		for (auto u : e[g]) if (u != p) dfs_par(dfs_par, u, g);
	}; dfs_par(dfs_par, a, -1);

	vector<ll> ancestor_list;
	ll x = b;
	while (x != -1) {
		ancestor_list.pb(x);
		x = par[x];
	}


	auto dfs_cost = [&](auto dfs_cost, ll g, ll p, ll avoid) -> ll {
		vector<ll> children_costs;
		for (auto u : e[g]) if (u != p and u != avoid) {
			children_costs.pb(dfs_cost(dfs_cost, u, g, avoid));
		}
		sort(all(children_costs));
		ll to_add = (int)children_costs.size(), mx = 0;
		for (auto u : children_costs) {
			mx = max(mx, to_add + u);
			to_add--;
		}
		return mx;
	};

	ll ans = dfs_cost(dfs_cost, a, -1, -1);
	auto process_cost = [&](ll mid) -> pii {
		ll up_to = ancestor_list[mid];
		ll cost_low = dfs_cost(dfs_cost, b, -1, par[up_to]);
		ll cost_high = dfs_cost(dfs_cost, a, -1, up_to);
		ans = min(ans, max(cost_low, cost_high));
		debug(up_to, cost_low, cost_high);
		return {cost_low, cost_high};
	};

	ll lo = 0, hi = (int)ancestor_list.size() - 2, mid;
	while (lo < hi) {
		mid = (lo + hi + 1) >> 1;
		auto [cost_low, cost_high] = process_cost(mid);
		if (cost_low <= cost_high) lo = mid;
		else hi = mid - 1;
	}
	process_cost(lo);

 	lo = 0, hi = (int)ancestor_list.size() - 2, mid;
	while (lo < hi) {
		mid = (lo + hi) >> 1;

		auto [cost_low, cost_high] = process_cost(mid);
		
		if (cost_high >= cost_low) hi = mid;
		else lo = mid + 1;
	}
	process_cost(lo);

	cout << ans << '\n';
	
}

int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);

	T = 1;
	//cin >> T;
	FOR(t, T)
		solve();

	cout.flush();
	return 0;
}

Compilation message

torrent.cpp: In lambda function:
torrent.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) "zzz"
      |                    ^~~~~
torrent.cpp:89:3: note: in expansion of macro 'debug'
   89 |   debug(up_to, cost_low, cost_high);
      |   ^~~~~
torrent.cpp: In function 'void solve()':
torrent.cpp:102:50: warning: right operand of comma operator has no effect [-Wunused-value]
  102 |   lo = 0, hi = (int)ancestor_list.size() - 2, mid;
      |                                                  ^

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 27672 KB Output is correct
2 Correct 669 ms 29552 KB Output is correct
3 Correct 664 ms 32376 KB Output is correct
4 Correct 666 ms 30412 KB Output is correct
5 Correct 665 ms 27184 KB Output is correct
6 Correct 617 ms 28076 KB Output is correct
7 Correct 571 ms 34340 KB Output is correct