oj.uz

Submission #926307

# Submission time Handle Problem Language Result Execution time Memory
926307 2024-02-12T19:03:43 Z rainboy ROI16_sending (ROI16_sending) C
0 / 100
 5000 ms 86084 KB 
#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) {
	if (r - l == 1)
		t = 0;
	else {
		int 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;

	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 main() {
	int h, i, j;

	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);
	d_ = 0, h1_ = 0, h2_ = 1, dfs3(0);
	printf("%d\n", d_);
	printf("%d %d\n", h1_ + 1, h2_ + 1);
	return 0;
}

Compilation message

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:248:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  248 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
sending.c:252:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  252 |   scanf("%d", &pp[i]), pp[i]--;
      |   ^~~~~~~~~~~~~~~~~~~
sending.c:260:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  260 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31068 KB Output is correct
2 Correct 3 ms 31068 KB Output is correct
3 Correct 3 ms 31068 KB Output is correct
4 Correct 3 ms 31068 KB Output is correct
5 Correct 3 ms 31068 KB Output is correct
6 Correct 3 ms 31068 KB Output is correct
7 Correct 4 ms 31068 KB Output is correct
8 Correct 3 ms 31172 KB Output is correct
9 Correct 4 ms 31068 KB Output is correct
10 Correct 3 ms 31156 KB Output is correct
11 Execution timed out 5079 ms 31168 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31068 KB Output is correct
2 Correct 3 ms 31068 KB Output is correct
3 Correct 3 ms 31068 KB Output is correct
4 Correct 3 ms 31068 KB Output is correct
5 Correct 3 ms 31068 KB Output is correct
6 Correct 3 ms 31068 KB Output is correct
7 Correct 4 ms 31068 KB Output is correct
8 Correct 3 ms 31172 KB Output is correct
9 Correct 4 ms 31068 KB Output is correct
10 Correct 3 ms 31156 KB Output is correct
11 Execution timed out 5079 ms 31168 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31068 KB Output is correct
2 Correct 3 ms 31068 KB Output is correct
3 Correct 3 ms 31068 KB Output is correct
4 Correct 3 ms 31068 KB Output is correct
5 Correct 3 ms 31068 KB Output is correct
6 Correct 3 ms 31068 KB Output is correct
7 Correct 4 ms 31068 KB Output is correct
8 Correct 3 ms 31172 KB Output is correct
9 Correct 4 ms 31068 KB Output is correct
10 Correct 3 ms 31156 KB Output is correct
11 Execution timed out 5079 ms 31168 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31068 KB Output is correct
2 Correct 3 ms 31068 KB Output is correct
3 Correct 3 ms 31068 KB Output is correct
4 Correct 3 ms 31068 KB Output is correct
5 Correct 3 ms 31068 KB Output is correct
6 Correct 3 ms 31068 KB Output is correct
7 Correct 4 ms 31068 KB Output is correct
8 Correct 3 ms 31172 KB Output is correct
9 Correct 4 ms 31068 KB Output is correct
10 Correct 3 ms 31156 KB Output is correct
11 Execution timed out 5079 ms 31168 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1242 ms 75852 KB Output is correct
2 Execution timed out 5100 ms 39760 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 75804 KB Output is correct
2 Correct 154 ms 75744 KB Output is correct
3 Correct 159 ms 86084 KB Output is correct
4 Correct 167 ms 81420 KB Output is correct
5 Correct 156 ms 80596 KB Output is correct
6 Execution timed out 5052 ms 76796 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31068 KB Output is correct
2 Correct 3 ms 31068 KB Output is correct
3 Correct 3 ms 31068 KB Output is correct
4 Correct 3 ms 31068 KB Output is correct
5 Correct 3 ms 31068 KB Output is correct
6 Correct 3 ms 31068 KB Output is correct
7 Correct 4 ms 31068 KB Output is correct
8 Correct 3 ms 31172 KB Output is correct
9 Correct 4 ms 31068 KB Output is correct
10 Correct 3 ms 31156 KB Output is correct
11 Execution timed out 5079 ms 31168 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31068 KB Output is correct
2 Correct 3 ms 31068 KB Output is correct
3 Correct 3 ms 31068 KB Output is correct
4 Correct 3 ms 31068 KB Output is correct
5 Correct 3 ms 31068 KB Output is correct
6 Correct 3 ms 31068 KB Output is correct
7 Correct 4 ms 31068 KB Output is correct
8 Correct 3 ms 31172 KB Output is correct
9 Correct 4 ms 31068 KB Output is correct
10 Correct 3 ms 31156 KB Output is correct
11 Execution timed out 5079 ms 31168 KB Time limit exceeded
12 Halted 0 ms 0 KB -