#1039957 (D) No.3031 曲面の向き付け

• 問題: No.3031 曲面の向き付け
• ユーザー: ジュ・ビオレ・グレイス
• 提出日時: 2025-01-30 20:13:55
• 言語: D (dmd 2.109.1)
• 結果: WA
• 実行時間: -
• コード長: 3,169 bytes
• コンパイル時間: 702 ms
• コンパイル使用メモリ: 88,644 KB
• 実行使用メモリ: 175,364 KB
• 最終ジャッジ日時: 2025-02-01 22:02:02
• 合計ジャッジ時間: 27,629 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

ファイルパターン	結果
sample	AC * 3 WA * 1
other	AC * 14 WA * 12 TLE * 3

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
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
            orientations[tri] = true;
            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
                res1 = recursively_set(neighborhood1, neighborhood1.perm(tri.B, true) == tri.A);
            }
            if (ts2.length != 0) {
                auto neighborhood2 = ts2.keys[0];
                // neighborhood2 must have the orientation  C -> B
                res2 = recursively_set(neighborhood2, neighborhood2.perm(tri.C, true) == tri.B);
            }
            if (ts3.length != 0) {
                auto neighborhood3 = ts3.keys[0];
                // neighborhood3 must have the orientation  A -> C
                res3 = recursively_set(neighborhood3, neighborhood3.perm(tri.A, true) == 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");
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX