Submission #698593

#	Time	Username	Problem	Language	Result	Execution time	Memory
698593		vjudge1	Torrent (COI16_torrent)	C++17	100 / 100	115 ms	26616 KiB

torrent

/* ...... */

#include <bits/stdc++.h>
using namespace std;

#define inl inline
typedef long long ll;
// typedef unsigned long long ull;
// typedef __int128 lll;
// typedef long double llf;
typedef pair <int, int> pint;
#define fst first
#define scd second
#define all(p) begin (p), end (p)
#define empb emplace_back
using vint = vector <int>;

constexpr int N = 3e5 + 10;
int n, x, y, a, b, seq[N], m; vint e[N];
bool ban[N]; int f[N], ffr[N];

bool sagasu (int x, int fr) {
	if (x == a) return seq[++m] = a, ban[x] = 1;
	for (const int y : e[x])
		if (y != fr && sagasu (y, x) == 1)
			return seq[++m] = x, ban[x] = 1;
	return 0;
}
void dp (int x, int fr) {
	vint lst; int c = 0;
	for (const int y : e[x])
		if (y != fr && !ban[y])
			dp (y, x), lst.empb (f[y]);
	sort (all (lst), greater <int> ());
	for (const int t : lst)
		if (f[x] <= t + ++c)
			f[x] = t + c, ffr[x] = t;
}
template <int dt>
inl int imple (int lmt) {
	for (int i = dt == 1 ? 1 : m, c = 0;
		i && i <= m; i += dt, ++c) {
		int x = seq[i];
		if (f[x] > lmt) return c;
		if (f[x] == lmt) lmt = ffr[x] - 1;
		else --lmt;
	}
	return m;
}

int main () {
	/*  */
	scanf ("%d%d%d", &n, &a, &b);
	for (int i = 1; i < n; ++i)
		scanf ("%d%d", &x, &y),
		e[x].empb (y), e[y].empb (x);
	sagasu (b, 0);
	for (int i = 1; i <= m; ++i)
		dp (seq[i], 0);
	int l = 0, r = n, mid;
	while (l < r) {
		mid = l + r >> 1;
		if (imple <1> (mid) + imple <-1> (mid) >= m) r = mid;
		else l = mid + 1;
	}
	printf ("%d", l);

	return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'int main()':
torrent.cpp:62:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |   mid = l + r >> 1;
      |         ~~^~~
torrent.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  scanf ("%d%d%d", &n, &a, &b);
      |  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:55:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf ("%d%d", &x, &y),
      |   ~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 31 / 31
• Subtask 2: 69 / 69