結果

問題 No.2274 三角彩色
コンテスト
ユーザー ジュ・ビオレ・グレイス
提出日時 2024-12-22 17:49:13
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 3,142 bytes
コンパイル時間 3,217 ms
コンパイル使用メモリ 116,224 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-22 17:49:18
合計ジャッジ時間 4,301 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.algorithm, std.array, std.conv, std.stdio, std.typecons;

alias F_2Vector = ulong[13];
static ulong_size = 8 * (ulong.sizeof);

void set_entry(ref F_2Vector vector, uint n_th, int val) {
	if (val)
		vector[n_th / ulong_size] |= 1UL << n_th % ulong_size;
	else
		vector[n_th / ulong_size] &= ~0UL - (1UL << (n_th % ulong_size));
}

bool is_zero(F_2Vector vector) {
	foreach (e; vector) if (e != 0) return false;
	return true;
}

F_2Vector slide_vector(F_2Vector vector) {
	F_2Vector slided;
	foreach (i; 0 .. vector.length - 1) {
		slided[i] = vector[i+1];
	}
	return slided;
}

// by sweep
// vectors can change
uint get_rank(F_2Vector[] vectors ...) {
	if (vectors.all!(v => is_zero(v))) return 0;
	
	// make the left-most vector nonzero
	while (vectors.all!(v => v[0] == 0))
		vectors.each!((ref v) => v = slide_vector(v));
	while (vectors.all!(v => v[0] % 2 == 0))
		vectors.each!((ref v) => v[0] >>= 1);
	foreach (ref v; vectors) {
		if (v[0] % 2 != 0) {
			auto tmp = vectors[0];
			vectors[0] = v;
			v = tmp;
		}
	}
	
	// sweeping
	foreach (ref v; vectors[1 .. $]) {
		if (v[0] % 2 != 0)
			v[] ^= vectors[0][];
	}
	
	vectors[1 .. $].map!((ref v) => v[0] >>= 1);
	return 1 + get_rank(vectors[1 .. $]);
}

alias Edge = Tuple!(uint, uint);
alias Face = Tuple!(uint, uint, uint);
alias Data = Tuple!(uint, "vertices", Edge[], "edges", Face[], "faces");	// vertices: number of vertices

Data normalize(ulong[2][] e, ulong[3][] f) {
	uint v;
	uint[ulong] vertices;
	Data data;
	
	foreach (edge; e) {
		if (edge[0] !in vertices)
			vertices[edge[0]] = v, ++v;
		if (edge[1] !in vertices)
			vertices[edge[1]] = v, ++v;
	}
	
	data.vertices = v;
	foreach (edge; e) {
		data.edges ~= Edge(vertices[edge[0]], vertices[edge[1]]);
	}
	foreach (face; f) {
		data.faces ~= Face(cast(uint)face[0], cast(uint)face[1], cast(uint)face[2]);
	}
	
	return data;
}

void main() {
	ulong M, B, Q;
	{
		auto tmp = readln().split().to!(ulong[]);
		M = tmp[1];
		B = tmp[2];
		Q = tmp[3];
	}
	ulong[2][] e;
	foreach (i; 0 .. M) {
		auto tmp = readln().split().to!(ulong[]);
		e.length += 1;
		e[$-1][0] = tmp[0];
		e[$-1][1] = tmp[1];
	}
	ulong[3][] f;
	foreach (i; 0 .. Q) {
		auto tmp = readln().split().to!(ulong[]);
		f.length += 1;
		f[$-1][0] = tmp[0];
		f[$-1][1] = tmp[1];
		f[$-1][2] = tmp[2];
	}
	//////////////////////////////
	auto data = normalize(e, f);
	
	// calculate all good colorings
	F_2Vector[] d_0_vectors;
	foreach (edge; data.edges) {
		F_2Vector vector;
		set_entry(vector, edge[0], 1);
		set_entry(vector, edge[1], 1);
		d_0_vectors ~= vector;
	}
	auto rank_d_0 = get_rank(d_0_vectors);
	auto dim_ker_d_0 = M - rank_d_0;
	
	// calculate T
	F_2Vector[] d_1_vectors;
	foreach (face; data.faces) {
		F_2Vector vector;
		set_entry(vector, face[0], 1);
		set_entry(vector, face[1], 1);
		set_entry(vector, face[2], 1);
		d_1_vectors ~= vector;
	}
	auto rank_d_1 = get_rank(d_1_vectors);
	
	auto ans_all = 1UL;
	foreach (i; 0 .. dim_ker_d_0) {
		ans_all = (ans_all * 2) % B;
	}
	auto ans_1 = 1UL;
	foreach (i; 0 .. rank_d_1) {
		ans_1 = (ans_1 * 2) % B;
	}
	ulong ans_0 = (B + ans_all - ans_1) % B; 
	writeln(ans_0, " ", ans_1);
}
0