結果

問題 No.971 いたずらっ子
コンテスト
ユーザー keymoon
提出日時 2020-01-17 21:41:45
言語 C#(csc)
(csc 3.9.0)
結果
MLE  
実行時間 -
コード長 4,300 bytes
コンパイル時間 1,848 ms
コンパイル使用メモリ 112,032 KB
実行使用メモリ 1,006,908 KB
最終ジャッジ日時 2024-06-25 19:10:26
合計ジャッジ時間 8,723 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other MLE * 1 -- * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;

public static class P
{
    public static void Main()
    {
        var hw = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var h = hw[0];
        var w = hw[1];
        var map = Enumerable.Repeat(0, h).Select(_ => Console.ReadLine()).ToArray().SelectMany(x => x).ToArray();

        //skip large case
        //if (10000 <= h * w) throw new Exception();

        int[] dists = new int[map.Length];

        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
            { var id = i * w + j; dists[id] = i + j; }

        List<int>[] graph = Enumerable.Repeat(0, h * w).Select(_ => new List<int>()).ToArray();
        for (int i = 0; i < h - 1; i++)
            for (int j = 0; j < w; j++)
            { var id = i * w + j; graph[id].Add(id + w); graph[id + w].Add(id); }
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w - 1; j++)
            { var id = i * w + j; graph[id].Add(id + 1); graph[id + 1].Add(id); }

        var shortest = Enumerable.Repeat(1L << 60, graph.Length).ToArray();
        PriorityQueue<Tuple> pqueue = new PriorityQueue<Tuple>();
        pqueue.Push(new Tuple(0, 0));
        while (0 < pqueue.Count)
        {
            var item = pqueue.Pop();
            if (shortest[item.Item1] != 1L << 60) continue;
            shortest[item.Item1] = item.Item2;
            foreach (var elem in graph[item.Item1])
            {
                if (shortest[elem] != 1L << 60) continue;
                pqueue.Push(new Tuple(elem, item.Item2 + 1 + (map[elem] == 'k' ? dists[elem] : 0)));
            }
        }
        Console.WriteLine(shortest.Last());
    }
}

struct Tuple : IComparable<Tuple>
{
    public int Item1;
    public int Item2;

    public Tuple(int item1, int item2)
    {
        Item1 = item1;
        Item2 = item2;
    }

    public int CompareTo(Tuple other) => Item2.CompareTo(other.Item2);
}


class PriorityQueue<T> where T : IComparable<T>
{
    public int Count { get; private set; }
    private bool Descendance;
    private T[] data = new T[65536];
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public PriorityQueue(bool descendance = false) { Descendance = descendance; }
    public T Top
    {
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        get { ValidateNonEmpty(); return data[1]; }
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public T Pop()
    {
        var top = Top;
        var elem = data[Count--];
        int index = 1;
        while (true)
        {
            if ((index << 1) >= Count)
            {
                if (index << 1 > Count) break;
                if (elem.CompareTo(data[index << 1]) > 0 ^ Descendance) data[index] = data[index <<= 1];
                else break;
            }
            else
            {
                var nextIndex = data[index << 1].CompareTo(data[(index << 1) + 1]) <= 0 ^ Descendance ? (index << 1) : (index << 1) + 1;
                if (elem.CompareTo(data[nextIndex]) > 0 ^ Descendance) data[index] = data[index = nextIndex];
                else break;
            }
        }
        data[index] = elem;
        return top;
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public void Push(T value)
    {
        int index = ++Count;
        if (data.Length == Count) Extend(data.Length * 2);
        while ((index >> 1) != 0)
        {
            if (data[index >> 1].CompareTo(value) > 0 ^ Descendance) data[index] = data[index >>= 1];
            else break;
        }
        data[index] = value;
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private void Extend(int newSize)
    {
        T[] newDatas = new T[newSize];
        data.CopyTo(newDatas, 0);
        data = newDatas;
    }
    private void ValidateNonEmpty() { if (Count == 0) throw new Exception(); }
}
0