結果
問題 | No.2431 Viral Hotel |
ユーザー |
|
提出日時 | 2023-08-18 23:00:45 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 495 ms / 2,000 ms |
コード長 | 5,206 bytes |
コンパイル時間 | 4,375 ms |
コンパイル使用メモリ | 115,352 KB |
実行使用メモリ | 55,236 KB |
最終ジャッジ日時 | 2024-11-28 09:32:57 |
合計ジャッジ時間 | 17,349 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 42 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
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[] NMi => ReadLine().Split().Select(c => int.Parse(c) - 1).ToArray();static int[][] NMap(int n) => Enumerable.Repeat(0, n).Select(_ => NMi).ToArray();static int[] LList(long n) => Enumerable.Repeat(0, (int)n).Select(_ => int.Parse(ReadLine())).ToArray();public static void Main(){Solve();}static void Solve(){var c = NList;var (n, k, m, p) = (c[0], c[1], c[2], c[3]);var map = NMap(m);var s = LList(n);var x = LList(k);var tree = new List<int>[n];for (var i = 0; i < tree.Length; ++i) tree[i] = new List<int>();foreach (var edge in map){tree[edge[0]].Add(edge[1]);tree[edge[1]].Add(edge[0]);}var q = new PriorityQueue<Pair>(n, false);var count = new int[n];foreach (var xi in x){++count[xi - 1];q.Enqueue(new Pair(xi - 1, 0, p));q.Enqueue(new Pair(xi - 1, 1, s[xi - 1]));// WriteLine($"day:0, v:{xi - 1}");}while (q.Count > 0){var date = q.List[0].Time;var move = new HashSet<int>();while (q.Count > 0 && q.List[0].Time == date){var cur = q.Dequeue();if (cur.Kind == 0 && count[cur.Pos] == 1){// recovercount[cur.Pos] = -1;// WriteLine($"day:{date}, recover:{cur.Pos}");}else if (cur.Kind == 1){// spreadif (count[cur.Pos] == 1 || count[cur.Pos] == -1){foreach (var next in tree[cur.Pos]){if (count[next] == 0){++count[next];q.Enqueue(new Pair(next, 0, date + p));q.Enqueue(new Pair(next, 1, date + s[next]));// WriteLine($"day:{date}, v:{next} from {cur.Pos}");}else if (count[next] == 1){move.Add(next);// WriteLine($"day:{date}, v:{next} from {cur.Pos}, moved");}}}}}foreach (var mi in move) count[mi] = 2;}WriteLine(count.Count(ci => ci > 1));}class Pair : IComparable<Pair>{public int Pos;public int Kind;public int Time;public Pair(int pos, int kind, int time){Pos = pos; Kind = kind; Time = time;}public int CompareTo(Pair b){var d = Time.CompareTo(b.Time);if (d != 0) return d;return Kind.CompareTo(b.Kind);}}class PriorityQueue<T> where T : IComparable<T>{public T[] List;public int Count;bool IsTopMax;public PriorityQueue(int count, bool isTopMax){IsTopMax = isTopMax;List = new T[Math.Max(128, count)];}public void Enqueue(T value){if (Count == List.Length){var newlist = new T[List.Length * 2];for (var i = 0; i < List.Length; ++i) newlist[i] = List[i];List = newlist;}var pos = Count;List[pos] = value;++Count;while (pos > 0){var parent = (pos - 1) / 2;if (Calc(List[parent], List[pos], true)) break;Swap(parent, pos);pos = parent;}}public T Dequeue(){--Count;Swap(0, Count);var pos = 0;while (true){var child = pos * 2 + 1;if (child >= Count) break;if (child + 1 < Count && Calc(List[child + 1], List[child], false)) ++child;if (Calc(List[pos], List[child], true)) break;Swap(pos, child);pos = child;}return List[Count];}bool Calc(T a, T b, bool equalVal){var ret = a.CompareTo(b);if (ret == 0 && equalVal) return true;return IsTopMax ? ret > 0 : ret < 0;}void Swap(int a, int b){var tmp = List[a];List[a] = List[b];List[b] = tmp;}}}