oj.uz

Submission #767325

# Submission time Handle Problem Language Result Execution time Memory
767325 2023-06-26T15:42:11 Z rainboy Shymbulak (IZhO14_shymbulak) C
100 / 100
 55 ms 14588 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	200000
#define INF	0x3f3f3f3f

int dd[N], kk[N];

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

void append(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 d_; long long k_;

void dfs(int i) {
	int o, d, k;

	if (eo_[i] != 1)
		return;
	eo_[i] = 0;
	d = dd[i] + 1, k = kk[i];
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (eo_[j] > 0) {
			if (d_ < dd[j] + d)
				d_ = dd[j] + d, k_ = 0;
			if (d_ == dd[j] + d)
				k_ += (long long) kk[j] * k;
			if (dd[j] < d)
				dd[j] = d, kk[j] = 0;
			if (dd[j] == d)
				kk[j] += k;
			eo_[j]--, dfs(j);
			return;
		}
	}
}

int main() {
	static int ii[N], dp[N], kp[N], dq[N], kq[N];
	int n, m, h, i, j, o, d;
	long long k;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < n; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		append(i, j), append(j, i);
	}
	memcpy(eo_, eo, n * sizeof *eo);
	for (i = 0; i < n; i++)
		dd[i] = 0, kk[i] = 1;
	for (i = 0; i < n; i++)
		dfs(i);
	m = 0;
	for (i = 0; i < n; i++)
		if (eo_[i] > 0) {
			while (eo_[i] > 0) {
				eo_[i] = 0, ii[m++] = i;
				for (o = eo[i]; o--; ) {
					j = ej[i][o];
					if (eo_[j] > 0) {
						i = j;
						break;
					}
				}
			}
			break;
		}
	if (m > 1) {
		d = -INF, k = 0;
		for (h = 0; h < m; h++) {
			i = ii[h];
			if (h == m / 2)
				d = -INF, k = 0;
			if (d < dd[i] - h)
				d = dd[i] - h, k = 0;
			if (d == dd[i] - h)
				k += kk[i];
			dp[h] = d, kp[h] = k;
		}
		d = -INF, k = 0;
		for (h = m - 1; h >= 0; h--) {
			i = ii[h];
			if (h == m / 2 - 1)
				d = -INF, k = 0;
			if (d < dd[i] - h)
				d = dd[i] - h, k = 0;
			if (d == dd[i] - h)
				k += kk[i];
			dq[h] = d, kq[h] = k;
		}
		for (h = 0; h < m; h++) {
			i = ii[h];
			if (h < m / 2) {
				if (h > 0) {
					d = dp[h - 1] + dd[i] + h, k = (long long) kp[h - 1] * kk[i];
					if (d_ < d)
						d_ = d, k_ = 0;
					if (d_ == d)
						k_ += k;
				}
				d = dq[h + (m + 1) / 2] + dd[i] + m + h, k = (long long) kq[h + (m + 1) / 2] * kk[i];
				if (d_ < d)
					d_ = d, k_ = 0;
				if (d_ == d)
					k_ += k;
			} else {
				if (h > m / 2) {
					d = dp[h - 1] + dd[i] + h, k = (long long) kp[h - 1] * kk[i];
					if (d_ < d)
						d_ = d, k_ = 0;
					if (d_ == d)
						k_ += k;
				}
				if (h + 1 < m || m % 2 == 0) {
					d = dq[h - m / 2] + dd[i] + h, k = (long long) kq[h - m / 2] * kk[i];
					if (d_ < d)
						d_ = d, k_ = 0;
					if (d_ == d)
						k_ += k;
				}
			}
		}
	}
	printf("%lld\n", k_);
	return 0;
}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 564 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 2 ms 720 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6544 KB Output is correct
2 Correct 33 ms 7460 KB Output is correct
3 Correct 24 ms 8020 KB Output is correct
4 Correct 20 ms 6992 KB Output is correct
5 Correct 20 ms 7124 KB Output is correct
6 Correct 55 ms 12376 KB Output is correct
7 Correct 35 ms 10444 KB Output is correct
8 Correct 40 ms 13996 KB Output is correct
9 Correct 41 ms 14140 KB Output is correct
10 Correct 42 ms 14588 KB Output is correct
11 Correct 41 ms 13860 KB Output is correct
12 Correct 44 ms 14492 KB Output is correct