Submission #767325

#	Time	Username	Problem	Language	Result	Execution time	Memory
767325		rainboy	Shymbulak (IZhO14_shymbulak)	C11	100 / 100	55 ms	14588 KiB

shymbulak

#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 (stderr)

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 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50