Submission #926345

#	Time	Username	Problem	Language	Result	Execution time	Memory
926345		rainboy	ROI16_sending (ROI16_sending)	C11	70 / 100	5022 ms	86608 KiB

sending

#include <stdio.h>
#include <stdlib.h>

#define N	200000
#define M	200000
#define L	19	/* L = ceil(log2(M * 2)) */
#define N_	(M * 2 * (L + 1) + 1)
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int *ej[N], eo[N], *eh[N], eo_[N], n;

void append(int **ej, int *eo, int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int dd[N], pp[N], qq[N], ta[N], tb[N];

int dfs1(int i, int d) {
	int o, s, k_, j_;

	dd[i] = d;
	s = 1, k_ = 0, j_ = -1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o], k = dfs1(j, d + 1);

		s += k;
		if (k_ < k)
			k_ = k, j_ = j;
	}
	qq[i] = j_;
	return s;
}

void dfs2(int i, int q) {
	static int time;
	int o, j_;

	ta[i] = time++;
	j_ = qq[i], qq[i] = q;
	if (j_ != -1)
		dfs2(j_, q);
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != j_)
			dfs2(j, j);
	}
	tb[i] = time;
}

int lca(int i, int j) {
	while (qq[i] != qq[j])
		if (dd[qq[i]] > dd[qq[j]])
			i = pp[qq[i]];
		else
			j = pp[qq[j]];
	return dd[i] < dd[j] ? i : j;
}

int ii[M * 2], idx[M * 2], m;

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = ta[ii[hh[j]]] - ta[ii[h]];

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		}
		sort(hh, l, i);
		l = k;
	}
}

int hh_[M * 2], dd1[M * 4], ddmn[M * 4];

void build(int l, int r) {
	int m;

	if (r - l == 1)
		ddmn[l + r] = INF;
	else {
		m = (l + r) / 2;
		build(l, m), build(m, r);
		ddmn[l + r] = min(min(ddmn[l + m], dd1[m]), ddmn[m + r]);
	}
}

int ll[N_], rr[N_], ddp[N_], ddq[N_], ddmx[N_];

int node(int l, int r, int i) {
	static int _ = 1;
	int t = _++;

	if (r - l == 1)
		ddp[t] = ddq[t] = INF, ddmx[t] = -1;
	else {
		int m = (l + r) / 2;

		if (i < m) {
			ll[t] = node(l, m, i);
			ddp[t] = ddp[ll[t]], ddq[t] = min(min(ddq[ll[t]], dd1[m]), ddmn[m + r]);
		} else {
			rr[t] = node(m, r, i);
			ddp[t] = min(min(ddmn[l + m], dd1[m]), ddp[rr[t]]), ddq[t] = ddq[rr[t]];
		}
		ddmx[t] = -1;
	}
	return t;
}

int remove_(int t, int l, int r, int i) {
	int m;

	if (r - l == 1)
		t = 0;
	else {
		m = (l + r) / 2;
		if (i < m)
			ll[t] = remove_(ll[t], l, m, i);
		else
			rr[t] = remove_(rr[t], m, r, i);
		if (ll[t] == 0 && rr[t] == 0)
			t = 0;
		else {
			ddp[t] = ll[t] ? ddp[ll[t]] : min(min(ddmn[l + m], dd1[m]), ddp[rr[t]]);
			ddq[t] = rr[t] ? ddq[rr[t]] : min(min(ddq[ll[t]], dd1[m]), ddmn[m + r]);
			ddmx[t] = max(max(ddmx[ll[t]], ddmx[rr[t]]), min(min(ddq[ll[t]], dd1[m]), ddp[rr[t]]));
		}
	}
	return t;
}

int merge(int t1, int t2, int l, int r) {
	int m;

	if (t1 == 0)
		return t2;
	if (t2 == 0)
		return t1;
	m = (l + r) / 2;
	ll[t1] = merge(ll[t1], ll[t2], l, m), rr[t1] = merge(rr[t1], rr[t2], m, r);
	ddp[t1] = ll[t1] ? ddp[ll[t1]] : min(min(ddmn[l + m], dd1[m]), ddp[rr[t1]]);
	ddq[t1] = rr[t1] ? ddq[rr[t1]] : min(min(ddq[ll[t1]], dd1[m]), ddmn[m + r]);
	ddmx[t1] = max(max(ddmx[ll[t1]], ddmx[rr[t1]]), min(min(ddq[ll[t1]], dd1[m]), ddp[rr[t1]]));
	return t1;
}

int find_p(int t, int l, int r) {
	int m;

	if (r - l == 1)
		return hh_[l] >> 1;
	m = (l + r) / 2;
	return ll[t] ? find_p(ll[t], l, m) : find_p(rr[t], m, r);
}

int find_q(int t, int l, int r) {
	int m;

	if (r - l == 1)
		return hh_[l] >> 1;
	m = (l + r) / 2;
	return rr[t] ? find_q(rr[t], m, r) : find_q(ll[t], l, m);
}

void find_mx(int t, int l, int r, int *h1, int *h2) {
	int m;

	m = (l + r) / 2;
	if (ddmx[ll[t]] == ddmx[t])
		find_mx(ll[t], l, m, h1, h2);
	else if (ddmx[rr[t]] == ddmx[t])
		find_mx(rr[t], m, r, h1, h2);
	else
		*h1 = find_q(ll[t], l, m), *h2 = find_p(rr[t], m, r);
}

int t_, d_, h1_, h2_;

void dfs3(int i) {
	static int hh[M * 2], tt[M * 2], dd1[M * 2];
	int m_, cnt, h, o, d, d1;

	if (eo_[i]) {
		m_ = 0;
		for (o = eo_[i]; o--; ) {
			h = eh[i][o];
			hh[m_++] = h << 1 | 0, hh[m_++] = h << 1 | 1;
		}
		sort(hh, 0, m_);
		cnt = 0;
		for (h = 0; h <= m_; h++) {
			d1 = h == 0 || h == m_ ? -1 : dd[lca(ii[hh[h]], ii[hh[h - 1]])];
			while (cnt >= 2 && dd1[cnt - 1] >= d1) {
				tt[cnt - 2] = merge(tt[cnt - 2], tt[cnt - 1], 0, m * 2);
				if (ddmx[tt[cnt - 2]] != -1) {
					d = dd1[cnt - 1] + ddmx[tt[cnt - 2]] - dd[i] * 2;
					if (d_ < d)
						d_ = d, find_mx(tt[cnt - 2], 0, m * 2, &h1_, &h2_);
				}
				cnt--;
			}
			if (h < m_)
				tt[cnt] = node(0, m * 2, idx[hh[h] ^ 1]), dd1[cnt] = d1, cnt++;
		}
		t_ = merge(t_, tt[0], 0, m * 2);
	}
	if (ddmx[t_] != -1) {
		d = ddmx[t_] - dd[i];
		if (d_ < d)
			d_ = d, find_mx(t_, 0, m * 2, &h1_, &h2_);
	}
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		dfs3(j);
	}
	for (o = eo_[i]; o--; ) {
		h = eh[i][o];
		t_ = remove_(t_, 0, m * 2, idx[h << 1 | 0]);
		t_ = remove_(t_, 0, m * 2, idx[h << 1 | 1]);
	}
}

int common(int h1, int h2) {
	int a1 = lca(ii[h1 << 1 | 0], ii[h1 << 1 | 1]);
	int a2 = lca(ii[h2 << 1 | 0], ii[h2 << 1 | 1]);

	if (a1 == a2)
		return max(dd[lca(ii[h1 << 1 | 0], ii[h2 << 1 | 0])] + dd[lca(ii[h1 << 1 | 1], ii[h2 << 1 | 1])], dd[lca(ii[h1 << 1 | 0], ii[h2 << 1 | 1])] + dd[lca(ii[h1 << 1 | 1], ii[h2 << 1 | 0])]) - dd[a1] * 2;
	else
		return max(max(max(dd[lca(ii[h1 << 1 | 0], ii[h2 << 1 | 0])], dd[lca(ii[h1 << 1 | 0], ii[h2 << 1 | 1])]), max(dd[lca(ii[h1 << 1 | 1], ii[h2 << 1 | 0])], dd[lca(ii[h1 << 1 | 1], ii[h2 << 1 | 1])])) - max(dd[a1], dd[a2]), 0);
}

int main() {
	int h, h1, h2, i, j, d;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (i = 1; i < n; i++) {
		scanf("%d", &pp[i]), pp[i]--;
		append(ej, eo, pp[i], i);
	}
	dfs1(0, 0);
	dfs2(0, 0);
	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (h = 0; h < m; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		ii[h << 1 | 0] = i, ii[h << 1 | 1] = j;
		append(eh, eo_, lca(i, j), h);
	}
	for (h = 0; h < m * 2; h++)
		hh_[h] = h;
	sort(hh_, 0, m * 2);
	for (h = 0; h < m * 2; h++)
		idx[hh_[h]] = h;
	for (h = 1; h < m * 2; h++)
		dd1[h] = dd[lca(ii[hh_[h - 1]], ii[hh_[h]])];
	build(0, m * 2);
	if (m <= 5000) {
		d_ = 0, h1_ = 0, h2_ = 1;
		for (h1 = 0; h1 < m; h1++)
			for (h2 = h1 + 1; h2 < m; h2++) {
				d = common(h1, h2);
				if (d_ < d)
					d_ = d, h1_ = h1, h2_ = h2;
			}
	} else {
		ddp[0] = -1, ddq[0] = -1, ddmx[0] = -1;
		d_ = 0, h1_ = 0, h2_ = 1, dfs3(0);
	}
	printf("%d\n", d_);
	printf("%d %d\n", h1_ + 1, h2_ + 1);
	return 0;
}

Compilation message (stderr)

sending.c: In function 'append':
sending.c:24:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   24 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
sending.c: In function 'main':
sending.c:261:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  261 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
sending.c:265:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  265 |   scanf("%d", &pp[i]), pp[i]--;
      |   ^~~~~~~~~~~~~~~~~~~
sending.c:273:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  273 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 29 / 29
• Subtask 2: 12 / 12
• Subtask 3: 7 / 7
• Subtask 4: 0 / 8
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 10