結果
問題 | No.1607 Kth Maximum Card |
ユーザー |
|
提出日時 | 2024-02-13 00:03:29 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 834 ms / 3,500 ms |
コード長 | 4,069 bytes |
コンパイル時間 | 6,756 ms |
コンパイル使用メモリ | 166,772 KB |
実行使用メモリ | 217,928 KB |
最終ジャッジ日時 | 2024-09-28 18:15:26 |
合計ジャッジ時間 | 17,830 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (82 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
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 c = NList;var (n, m, k) = (c[0], c[1], c[2]);var map = NArr(m);var tree = new List<(int to, int num)>[n];for (var i = 0; i < n; ++i) tree[i] = new List<(int to, int num)>();foreach (var edge in map){tree[edge[0] - 1].Add((edge[1] - 1, edge[2]));tree[edge[1] - 1].Add((edge[0] - 1, edge[2]));}var ok = 200001;var ng = -1;while (ok - ng > 1){var mid = (ok + ng) / 2;if (Check(tree, k, mid)) ok = mid;else ng = mid;}WriteLine(ok);}static bool Check(List<(int to, int num)>[] tree, int k, int mid){var q = new Deque<(int pos, int len)>();q.Enqueue((0, 0));var len = Enumerable.Repeat(int.MaxValue / 2, tree.Length).ToArray();len[0] = 0;while (q.Count > 0){var cur = q.Dequeue();if (cur.len != len[cur.pos]) continue;foreach (var next in tree[cur.pos]){var cost = next.num > mid ? 1 : 0;if (len[next.to] <= cur.len + cost) continue;len[next.to] = cur.len + cost;if (cost == 0) q.PushFront((next.to, len[next.to]));else q.Enqueue((next.to, len[next.to]));}}return len[^1] < k;}/// 前後から出し入れ可能なキューclass Deque<T>{int _s = 0;int _t = 0;T[] _arr;public Deque() : this(4){}public Deque(int size){_arr = new T[size];}public Deque(IEnumerable<T> init){var list = init.ToArray();var size = 4;while (size <= list.Length) size <<= 1;_arr = new T[size];for (var i = 0; i < list.Length; ++i) _arr[i] = list[i];_t = _arr.Length;}public int Count{get { return (_t + _arr.Length - _s) % _arr.Length; }}public void Enqueue(T item){if (Count + 1 == _arr.Length) Expand();if (_t == _arr.Length) _t = 0;_arr[_t++] = item;}public T Dequeue(){var ret = _arr[_s++];if (_s == _arr.Length) _s = 0;return ret;}public void Push(T item){Enqueue(item);}public void PushFront(T item){if (Count + 1 == _arr.Length) Expand();if (_s == 0) _s = _arr.Length;_arr[--_s] = item;}public T Pop(){var ret = _arr[--_t];if (_t == 0) _t = _arr.Length;return ret;}public T Peek(){if (Count == 0) throw new InvalidOperationException("deque is empty");return _arr[_s];}void Expand(){var count = Count;var na = new T[_arr.Length * 2];var cur = 0;if (_s <= _t){for (var i = _s; i < _t; ++i) na[cur++] = _arr[i];}else{for (var i = _s; i < _arr.Length; ++i) na[cur++] = _arr[i];for (var i = 0; i < _t; ++i) na[cur++] = _arr[i];}_s = 0;_t = count;_arr = na;}}}