Submission #544741

#	Time	Username	Problem	Language	Result	Execution time	Memory
544741		rainboy	Paths (BOI18_paths)	C11	100 / 100	282 ms	43500 KiB

paths

#include <stdio.h>

#define N	300000
#define M	300000
#define K	5

int main() {
	static int cc[N], ii[M], jj[M];
	static long long dp[1 << K][N];
	int n, m, k, h, i, j, b;
	long long ans;

	scanf("%d%d%d", &n, &m, &k);
	for (i = 0; i < n; i++)
		scanf("%d", &cc[i]), cc[i]--;
	for (h = 0; h < m; h++)
		scanf("%d%d", &ii[h], &jj[h]), ii[h]--, jj[h]--;
	for (i = 0; i < n; i++)
		dp[1 << cc[i]][i] = 1;
	for (b = 0; b < 1 << k; b++)
		for (h = 0; h < m; h++) {
			i = ii[h], j = jj[h];
			if (!(b & 1 << cc[j]))
				dp[b | 1 << cc[j]][j] += dp[b][i];
			if (!(b & 1 << cc[i]))
				dp[b | 1 << cc[i]][i] += dp[b][j];
		}
	ans = 0;
	for (b = 0; b < 1 << k; b++)
		if (b & b - 1)
			for (i = 0; i < n; i++)
				ans += dp[b][i];
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

paths.c: In function 'main':
paths.c:30:13: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   30 |   if (b & b - 1)
      |           ~~^~~
paths.c:13:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%d%d%d", &n, &m, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
paths.c:15:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%d", &cc[i]), cc[i]--;
      |   ^~~~~~~~~~~~~~~~~~~
paths.c:17:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   scanf("%d%d", &ii[h], &jj[h]), ii[h]--, jj[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30