結果

問題 No.1614 Majority Painting on Tree
ユーザー 👑 ygussany
提出日時 2021-05-22 17:08:51
言語 C
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,042 bytes
コンパイル時間 141 ms
コンパイル使用メモリ 31,488 KB
実行使用メモリ 19,648 KB
最終ジャッジ日時 2024-07-17 15:08:45
合計ジャッジ時間 13,001 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

const int Mod = 998244353;

typedef struct List {
	struct List *next;
	int v, id;
} list;

long long naive(int N, int C, list* adj[], list e[])
{
	if (C == 1) return 1;
	
	int i, u, w, c[100001] = {}, num[256], sum = 0;
	long long ans = 0;
	list *p;
	while (c[N-1] == 0) {
		for (u = 1; u <= N; u++) {
			for (i = 0; i < C; i++) num[i] = 0;
			for (p = adj[u], sum = 0; p != NULL; p = p->next) {
				num[c[p->id]]++;
				sum++;
			}
			for (i = 0; i < C; i++) if (num[i] < sum && num[i] > sum / 2) break;
			if (i < C) break;
		}
		if (u > N) ans++;
		
		for (i = 0; c[i] == C - 1; c[i++] = 0);
		c[i]++;
	}
	return ans % Mod;
}

int main()
{
	int i, N, C, u, w;
	scanf("%d %d", &N, &C);
    list *adj[100001] = {}, e[200001];
	for (i = 0; i < N - 1; i++) {
		scanf("%d %d", &u, &w);
		e[i*2].v = w;
		e[i*2+1].v = u;
		e[i*2].id = i;
		e[i*2+1].id = i;
		e[i*2].next = adj[u];
		e[i*2+1].next = adj[w];
		adj[u] = &(e[i*2]);
		adj[w] = &(e[i*2+1]);
	}
	printf("%lld\n", naive(N, C, adj, e));
	fflush(stdout);
	return 0;
}
0