Submission #545942

#	Time	Username	Problem	Language	Result	Execution time	Memory
545942		rainboy	Star Trek (CEOI20_startrek)	C11	100 / 100	87 ms	18388 KiB

startrek

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

#define N	100000
#define MD	1000000007

int *ej[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;
}

char dp[N], dq[N]; int dr[N][2], ds[N][2];

void dfs1(int p, int i) {
	int o, j_, sum0, sum1;

	dp[i] = 0, j_ = -1, sum0 = 0, sum1 = 0;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p) {
			dfs1(i, j);
			sum0 += dr[j][0], sum1 += dr[j][1];
			if (!dp[j]) {
				dp[i] = 1;
				if (j_ == -1)
					j_ = j;
				else
					j_ = -2;
			}
		}
	}
	if (j_ == -1)
		dr[i][0] = sum1, dr[i][1] = sum0 + 1;
	else if (j_ != -2)
		dr[i][0] = dr[j_][1], dr[i][1] = sum0 + sum1 - dr[j_][1] + 1;
	else
		dr[i][0] = 0, dr[i][1] = sum0 + sum1 + 1;
}

void dfs2(int p, int i) {
	int o, j1, j2, sum0, sum1;

	j1 = -1, j2 = -1, sum0 = ds[i][0], sum1 = ds[i][1];
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p) {
			sum0 += dr[j][0], sum1 += dr[j][1];
			if (!dp[j]) {
				if (j1 == -1)
					j1 = j;
				else if (j2 == -1)
					j2 = j;
				else
					j1 = j2 = -2;
			}
		}
	}
	if (dq[i])
		for (o = eo[i]; o--; ) {
			int j = ej[i][o];

			if (j != p) {
				int sum0_ = sum0 - dr[j][0], sum1_ = sum1 - dr[j][1];

				if (j1 == -1 || j2 == -1 && j == j1)
					dq[j] = 0, ds[j][0] = sum1_, ds[j][1] = sum0_ + 1;
				else if (j2 == -1 || j == j2)
					dq[j] = 1, ds[j][0] = dr[j1][1], ds[j][1] = sum0_ + sum1_ - dr[j1][1] + 1;
				else if (j == j1)
					dq[j] = 1, ds[j][0] = dr[j2][1], ds[j][1] = sum0_ + sum1_ - dr[j2][1] + 1;
				else
					dq[j] = 1, ds[j][0] = 0, ds[j][1] = sum0_ + sum1_ + 1;
			}
		}
	else
		for (o = eo[i]; o--; ) {
			int j = ej[i][o];

			if (j != p) {
				int sum0_ = sum0 - dr[j][0], sum1_ = sum1 - dr[j][1];

				dq[j] = 1;
				if (j1 == -1 || j2 == -1 && j == j1)
					ds[j][0] = ds[i][1], ds[j][1] = sum0_ + sum1_ - ds[i][1] + 1;
				else
					ds[j][0] = 0, ds[j][1] = sum0_ + sum1_ + 1;
			}
		}
	if (dq[i]) {
		if (j1 == -1)
			dr[i][0] = sum1, dr[i][1] = sum0 + 1;
		else if (j2 == -1)
			dr[i][0] = dr[j1][1], dr[i][1] = sum0 + sum1 - dr[j1][1] + 1;
		else
			dr[i][0] = 0, dr[i][1] = sum0 + sum1 + 1;
	} else {
		dp[i] = 1;
		if (j1 == -1)
			dr[i][0] = ds[i][1], dr[i][1] = sum0 + sum1 - ds[i][1] + 1;
		else
			dr[i][0] = 0, dr[i][1] = sum0 + sum1 + 1;
	}
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p)
			dfs2(i, j);
	}
}

void mult(int aa[][2], int bb[][2], int cc[][2]) {
	cc[0][0] = ((long long) aa[0][0] * bb[0][0] + (long long) aa[0][1] * bb[1][0]) % MD;
	cc[0][1] = ((long long) aa[0][0] * bb[0][1] + (long long) aa[0][1] * bb[1][1]) % MD;
	cc[1][0] = ((long long) aa[1][0] * bb[0][0] + (long long) aa[1][1] * bb[1][0]) % MD;
	cc[1][1] = ((long long) aa[1][0] * bb[0][1] + (long long) aa[1][1] * bb[1][1]) % MD;
}

void power(int aa[][2], int pp[][2], int tt[][2], long long k) {
	if (k == 0) {
		pp[0][0] = 1, pp[0][1] = 0;
		pp[1][0] = 0, pp[1][1] = 1;
		return;
	}
	if (k % 2 == 0) {
		power(aa, tt, pp, k / 2);
		mult(tt, tt, pp);
	} else {
		power(aa, pp, tt, k / 2);
		mult(pp, pp, tt);
		mult(tt, aa, pp);
	}
}

int main() {
	static int aa[2][2], pp[2][2], tt[2][2];
	int n, h, i, j, x, y, k0, k1, ans;
	long long d;

	scanf("%d%lld", &n, &d);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		append(i, j), append(j, i);
	}
	dfs1(-1, 0);
	dq[0] = 1;
	dfs2(-1, 0);
	k0 = k1 = 0;
	for (i = 0; i < n; i++) {
		aa[0][0] = (aa[0][0] + dr[i][0]) % MD;
		aa[1][0] = (aa[1][0] + dr[i][1]) % MD;
		if (!dp[i])
			k0++, aa[0][1] = (aa[0][1] + n) % MD;
		else
			k1++, aa[1][1] = (aa[1][1] + n) % MD;
	}
	power(aa, pp, tt, d - 1);
	x = ((long long) pp[0][0] * k0 + (long long) pp[0][1] * k1) % MD;
	y = ((long long) pp[1][0] * k0 + (long long) pp[1][1] * k1) % MD;
	ans = 0;
	if (dp[0])
		ans = (ans + (long long) n * y) % MD;
	ans = (ans + (long long) dr[0][1] * x) % MD;
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

startrek.c: In function 'append':
startrek.c:12:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   12 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
startrek.c: In function 'dfs2':
startrek.c:72:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   72 |     if (j1 == -1 || j2 == -1 && j == j1)
      |                     ~~~~~~~~~^~~~~~~~~~
startrek.c:90:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   90 |     if (j1 == -1 || j2 == -1 && j == j1)
      |                     ~~~~~~~~~^~~~~~~~~~
startrek.c: In function 'main':
startrek.c:146:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |  scanf("%d%lld", &n, &d);
      |  ^~~~~~~~~~~~~~~~~~~~~~~
startrek.c:150:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 15 / 15