結果

問題 No.3031 曲面の向き付け
コンテスト
ユーザー kakel-san
提出日時 2025-02-21 23:42:42
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 444 ms / 2,000 ms
コード長 4,058 bytes
コンパイル時間 7,678 ms
コンパイル使用メモリ 170,004 KB
実行使用メモリ 235,636 KB
最終ジャッジ日時 2025-02-21 23:43:03
合計ジャッジ時間 16,568 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 29
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (127 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static int NN => int.Parse(ReadLine());
    static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
    static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var n = NN;
        var map = NArr(n);
        WriteLine(Order(n, map) ? "YES" : "NO");
    }
    static bool Order(int n, int[][] map)
    {
        var dic = new Dictionary<Bi, List<int>>();
        for (var i = 0; i < map.Length; ++i)
        {
            var b1 = new Bi(map[i][0], map[i][1]);
            if (dic.ContainsKey(b1)) dic[b1].Add(i);
            else dic[b1] = new List<int>() { i };
            var b2 = new Bi(map[i][1], map[i][2]);
            if (dic.ContainsKey(b2)) dic[b2].Add(i);
            else dic[b2] = new List<int>() { i };
            var b3 = new Bi(map[i][0], map[i][2]);
            if (dic.ContainsKey(b3)) dic[b3].Add(i);
            else dic[b3] = new List<int>() { i };
        }
        foreach (var kv in dic)
        {
            if (kv.Value.Count > 2)
            {
                return false;
            }
        }
        var orders = new int[n];
        for (var i = 0; i < n; ++i) if (orders[i] == 0)
        {
            var q = new Queue<(int id, int o)>();
            q.Enqueue((i, 1));
            orders[i] = 1;
            while (q.Count > 0)
            {
                var cur = q.Dequeue();
                var b1 = new Bi(map[cur.id][0], map[cur.id][1]);
                if (dic[b1].Count == 2)
                {
                    var o = Other(dic[b1], cur.id);
                    var nv = orders[cur.id] * (IsFlip(map[cur.id], map[o], b1.A, b1.B) ? -1 : 1);
                    if (orders[o] == 0)
                    {
                        orders[o] = nv;
                        q.Enqueue((o, orders[o]));
                    }
                    else if (orders[o] != nv) return false;
                }
                var b2 = new Bi(map[cur.id][1], map[cur.id][2]);
                if (dic[b2].Count == 2)
                {
                    var o = Other(dic[b2], cur.id);
                    var nv = orders[cur.id] * (IsFlip(map[cur.id], map[o], b2.A, b2.B) ? -1 : 1);
                    if (orders[o] == 0)
                    {
                        orders[o] = nv;
                        q.Enqueue((o, orders[o]));
                    }
                    else if (orders[o] != nv) return false;
                }
                var b3 = new Bi(map[cur.id][0], map[cur.id][2]);
                if (dic[b3].Count == 2)
                {
                    var o = Other(dic[b3], cur.id);
                    var nv = orders[cur.id] * (IsFlip(map[cur.id], map[o], b3.A, b3.B) ? -1 : 1);
                    if (orders[o] == 0)
                    {
                        orders[o] = nv;
                        q.Enqueue((o, orders[o]));
                    }
                    else if (orders[o] != nv) return false;
                }
            }
        }
        return true;
    }
    static bool IsFlip(int[] a, int[] b, int x, int y)
    {
        var ans = true;
        if (a[0] == x && a[2] == y) ans = !ans;
        if (b[0] == x && b[2] == y) ans = !ans;
        return ans;
    }
    static int Other(List<int> list, int a)
    {
        return list[0] == a ? list[1] : list[0];
    }
    class Bi
    {
        public int A;
        public int B;
        public Bi(int a, int b)
        {
            A = a; B = b;
        }
        public override bool Equals(object obj)
        {
            var o = (Bi) obj;
            return A == o.A && B == o.B;
        }
        public override int GetHashCode()
        {
            return (int)((A * 100_000_000L + B) % 1_000_000_007);
        }
    }
}
0