結果

問題 No.3031 曲面の向き付け
コンテスト
ユーザー ジュ・ビオレ・グレイス
提出日時 2025-01-30 20:23:12
言語 D
(dmd 2.109.1)
結果
TLE  
実行時間 -
コード長 3,394 bytes
コンパイル時間 931 ms
コンパイル使用メモリ 90,464 KB
実行使用メモリ 173,332 KB
最終ジャッジ日時 2025-02-01 22:02:41
合計ジャッジ時間 48,596 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19 TLE * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

alias Edge = Tuple!(uint, uint);	// must be sorted

struct Triangle {
	// assert(A < B && B < C)
	uint A, B, C;
	this (uint a, uint b, uint c) {
		A = a, B = b, C = c;
	}
	
	// X is A, B or C
	// true: A->B->C, false: A->C->B
	uint perm(uint X, bool orientation) {
		if (orientation) {
			if      (X == A) return B;
			else if (X == B) return C;
			else if (X == C) return A;
			else assert(0);
		}
		else {
			if      (X == B) return A;
			else if (X == C) return B;
			else if (X == A) return C;
			else assert(0);
		}
	}
}

bool solve(bool[Triangle] triangle_set) {
	// the map from edge to triangles
	bool[Triangle][Edge] edge_to_triangles;
	foreach (triangle, _; triangle_set)
		foreach (edge; [Edge(triangle.A, triangle.B), Edge(triangle.B, triangle.C), Edge(triangle.A, triangle.C)] )
			if (edge in edge_to_triangles)
				edge_to_triangles[edge][triangle] = true;
			else
				edge_to_triangles[edge] = [triangle: true];
	
	// check if some more than triangles share a single edge
	if (edge_to_triangles.values.any!(ts => ts.length > 2)) return false;
	
	// unoriented triangles
	auto unoriented = triangle_set.dup;
	// orientations that are determined
	bool[Triangle] orientations;
	// return: true = compatiblly set
	bool recursively_set(Triangle tri, bool ori) {
		// already appears
		if (tri in orientations) {
			if (orientations[tri] == ori) return true;		// compatible
			else return false;								// not compatible
		}
		// first time appears
		else {
			// tri has orientation
			// A -> B -> C -> A (if ori == true)
			// A -> C -> B -> A (if ori == false)
			orientations[tri] = ori;
			unoriented.remove(tri);
			// three edges
			auto edge1 = Edge(tri.A, tri.B), edge2 = Edge(tri.B, tri.C), edge3 = Edge(tri.A, tri.C);
			// the triangles that is next to 'triangle'
			auto ts1 = edge_to_triangles[edge1].dup, ts2 = edge_to_triangles[edge2].dup, ts3 = edge_to_triangles[edge3].dup;
			ts1.remove(tri), ts2.remove(tri), ts3.remove(tri);
			// results
			auto res1 = true, res2 = true, res3 = true;
			
			if (ts1.length != 0) {
				auto neighborhood1 = ts1.keys[0];
				// neighborhood1 must have the orientation
				// B -> A (if ori == true)
				// A -> B (if ori == false)
				res1 = recursively_set(neighborhood1, neighborhood1.perm(tri.B, ori) == tri.A);
			}
			if (ts2.length != 0) {
				auto neighborhood2 = ts2.keys[0];
				// neighborhood1 must have the orientation
				// C -> B (if ori == true)
				// B -> C (if ori == false)
				res2 = recursively_set(neighborhood2, neighborhood2.perm(tri.C, ori) == tri.B);
			}
			if (ts3.length != 0) {
				auto neighborhood3 = ts3.keys[0];
				// neighborhood1 must have the orientation
				// A -> C (if ori == true)
				// C -> A (if ori == false)
				res3 = recursively_set(neighborhood3, neighborhood3.perm(tri.A, ori) == tri.C);
			}
			return res1 && res2 && res3;
		}
	}
	
	while (unoriented.length > 0) {
		auto uot = unoriented.keys[0];
		if (!recursively_set(uot, true)) return false;
	}
	
	return true;
}

void main() {
	// read
	auto M = readln[0 .. $-1].to!uint;
	
	// get the set of triangles
	bool[Triangle] triangle_set;
	foreach (m; 0 .. M) {
		auto ABC = readln.split.to!(uint[]);
		assert(ABC[0] < ABC[1] && ABC[1] < ABC[2]);
		triangle_set[Triangle(ABC[0], ABC[1], ABC[2])] = true;
	}
	
	writeln(triangle_set.solve ? "YES" : "NO");
}
0