Submission #763948

#	Time	Username	Problem	Language	Result	Execution time	Memory
763948		maomao90	Torrent (COI16_torrent)	C++17	100 / 100	491 ms	32768 KiB

torrent

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

#define REP(i, j, k) for (int i = (j); i < (k); i++)
#define RREP(i, j, k) for (int i = (j); i >= (k); i--)

template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}

typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef tuple<int, int, int> iii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXN = 300005;

int n, a, b;
vi adj[MAXN];

int pre[MAXN], pst[MAXN], ptr;
void dfs(int u, int p) {
	pre[u] = ptr++;
	for (int v : adj[u]) {
		if (v == p) {
			continue;
		}
		dfs(v, u);
	}
	pst[u] = ptr;
}

int pmx[MAXN], smx[MAXN];
int memo1[MAXN];
bool done[MAXN];
void dp1(int u, int p, int x) {
	int funny = 0;
	vi ch;
	for (int v : adj[u]) {
		if (v == p) {
			continue;
		}
		if (pre[v] <= pre[b] && pre[b] < pst[v]) {
			funny = v;
			continue;
		}
		ch.pb(v);
		dp1(v, u, x);
	}
	sort(ALL(ch), [&] (int l, int r) {
			return memo1[l] > memo1[r];
			});
	if (!funny) {
		REP (i, 0, SZ(ch)) {
			mxto(memo1[u], memo1[ch[i]] + i + 1);
		}
		return;
	}
	cerr << u << ' ' << p << ' ' << x << '\n';
	REP (i, 0, SZ(ch)) {
		cerr << ' ' << ch[i] << ": " << memo1[ch[i]] << '\n';
	}
	REP (i, 0, SZ(ch)) {
		pmx[i] = memo1[ch[i]] + i + 1;
		if (i) {
			mxto(pmx[i], pmx[i - 1]);
		}
		cerr << ' ' << i << ": " << pmx[i] << '\n';
	}
	RREP (i, SZ(ch) - 1, 0) {
		smx[i] = memo1[ch[i]] + i + 2;
		if (i + 1 != SZ(ch)) {
			mxto(smx[i], smx[i + 1]);
		}
		cerr << ' ' << i << ": " << smx[i] << '\n';
	}
	int gd = -1;
	REP (i, 0, SZ(ch) + 1) {
		int cmx = 0;
		if (i) {
			mxto(cmx, pmx[i - 1]);
		}
		if (i != SZ(ch)) {
			mxto(cmx, smx[i]);
		}
		cerr << "  " << i << ": " << cmx << '\n';
		if (cmx <= x) {
			gd = i;
			break;
		}
	}
	if (gd == -1) {
		return;
	}
	done[u] = 1;
	dp1(funny, u, x - (gd + 1));
}

int memo2[MAXN];
void dp2(int u, int p) {
	vi ch;
	for (int v : adj[u]) {
		if (v == p || done[v]) {
			continue;
		}
		ch.pb(v);
		dp2(v, u);
	}
	sort(ALL(ch), [&] (int l, int r) {
			return memo2[l] > memo2[r];
			});
	REP (i, 0, SZ(ch)) {
		mxto(memo2[u], memo2[ch[i]] + i + 1);
	}
}

bool isPos(int x) {
	REP (i, 1, n + 1) {
		done[i] = 0;
		memo1[i] = 0;
		memo2[i] = 0;
	}
	dp1(a, -1, x);
	if (!done[a]) {
		return 0;
	}
	dp2(b, -1);
	return memo2[b] <= x;
}

int main() {
#ifndef DEBUG
	ios::sync_with_stdio(0), cin.tie(0);
#endif
	cin >> n >> a >> b;
	REP (i, 1, n) {
		int u, v; cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	if (n == 2) {
		cout << 0 << '\n';
		return 0;
	}
	dfs(a, -1);
	int lo = 1, hi = n, mid;
	while (lo < hi) {
		mid = lo + hi >> 1;
		if (isPos(mid)) {
			hi = mid;
		} else {
			lo = mid + 1;
		}
	}
	cout << hi << '\n';
	return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'int main()':
torrent.cpp:165:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  165 |   mid = lo + hi >> 1;
      |         ~~~^~~~

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