結果

問題 No.3031 曲面の向き付け
コンテスト
ユーザー ジュ・ビオレ・グレイス
提出日時 2025-02-01 16:54:45
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 335 ms / 2,000 ms
コード長 3,579 bytes
コンパイル時間 963 ms
コンパイル使用メモリ 94,768 KB
実行使用メモリ 61,740 KB
最終ジャッジ日時 2025-02-01 22:01:52
合計ジャッジ時間 7,439 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

class Triangle {
	uint A, B, C;
	Triangle nAB, nBC, nAC;		// the triangles that share the edges
	int orientation;
	this (uint a, uint b, uint c) {
		A = a, B = b, C = c;
		assert(A < B && B < C);
	}
	
	// false if already set
	void set_neighborhood(Triangle n, uint P, uint Q) {
		if      (tuple(P, Q) == tuple(A, B)) {
			nAB = n;
		}
		else if (tuple(P, Q) == tuple(B, C)) {
			nBC = n;
		}
		else if (tuple(P, Q) == tuple(A, C)) {
			nAC = n;
		}
		else assert(0);
	}
	
	// X is A, B or C
	// 1: A->B->C, -1: A->C->B
	uint perm(uint X, int o = 0) {
		if (o == 0) o = this.orientation;
		if (o == 1) {
			if      (X == A) return B;
			else if (X == B) return C;
			else if (X == C) return A;
			else assert(0);
		}
		else if (o == -1) {
			if      (X == B) return A;
			else if (X == C) return B;
			else if (X == A) return C;
			else assert(0);
		}
		else assert(0);
	}
}

class Triangulation {
	Triangle[] triangles;
	bool unorientable = false;
	
	this(uint[][] tri_array) {
		// remove multiple appearance
		bool[Tuple!(uint, uint, uint)] triangle_set;
		foreach (tri3; tri_array) {
			triangle_set[tuple(tri3[0], tri3[1], tri3[2])] = true;
		}
		this.triangles = triangle_set.keys.map!(t => new Triangle(t[0], t[1], t[2])).array;
		
		// set neighborhoods
		Triangle[Tuple!(uint, uint)] edges;
		uint[Tuple!(uint, uint)] edge_appear_times;
		foreach (triangle; triangles) {
			foreach (edge; [tuple(triangle.A, triangle.B), tuple(triangle.B, triangle.C), tuple(triangle.A, triangle.C)]) {
				if (auto neiborhood = edge in edges) {
					// shared by three triangles
					if (edge_appear_times[edge] >= 2) {
						unorientable = true;
						return;
					}
					// set neighborhoods
					edge_appear_times[edge]++;
					triangle.set_neighborhood(*neiborhood, edge[0], edge[1]);
					neiborhood.set_neighborhood(triangle, edge[0], edge[1]);
				}
				else {
					// set neighborhoods
					edges[edge] = triangle;
					edge_appear_times[edge] = 1;
				}
			}
		}
	}
	
	// DFS
	void give_orientation(Triangle triangle, uint P, uint Q) {
		// already set
		if (!triangle || triangle.orientation != 0) return;
		
		triangle.orientation = triangle.perm(P, 1) == Q ? 1 : -1;
		
		// recursively
		if (triangle.perm(triangle.A) == triangle.B)
			give_orientation(triangle.nAB, triangle.B, triangle.A);
		else
			give_orientation(triangle.nAB, triangle.A, triangle.B);
		if (triangle.perm(triangle.B) == triangle.C)
			give_orientation(triangle.nBC, triangle.C, triangle.B);
		else
			give_orientation(triangle.nBC, triangle.B, triangle.C);
		if (triangle.perm(triangle.A) == triangle.C)
			give_orientation(triangle.nAC, triangle.C, triangle.A);
		else
			give_orientation(triangle.nAC, triangle.A, triangle.C);
	}
	
	bool is_orientable() {
		if (unorientable) return false;
		foreach (triangle; triangles) {
			give_orientation(triangle, triangle.A, triangle.B);
		}
		// check
		foreach (triangle; triangles) {
			with (triangle)
			// A -> B -> C -> A
			if (orientation == 1) {
				if ((nAB && nAB.perm(B) != A) || (nBC && nBC.perm(C) != B) || (nAC && nAC.perm(A) != C)) return false;
			}
			// A -> C -> B -> A
			else if (orientation == -1) {
				if ((nAB && nAB.perm(A) != B) || (nBC && nBC.perm(B) != C) || (nAC && nAC.perm(C) != A)) return false;
			}
			else assert (0);
		}
		return true;
	}
}

void main() {
	auto M = readln[0 .. $-1].to!uint;
	uint[][] tris;
	foreach (m; 0 .. M)
		tris ~= readln.split.to!(uint[]);
	auto trig = new Triangulation(tris);
	writeln(trig.is_orientable ? "YES" : "NO");
}
0