結果
| 問題 | No.994 ばらばらコイン |
| ユーザー |
 mnzn
|
| 提出日時 | 2020-05-07 01:59:32 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 10,794 bytes |
| コンパイル時間 | 870 ms |
| コンパイル使用メモリ | 64,652 KB |
| 実行使用メモリ | 47,320 KB |
| 最終ジャッジ日時 | 2023-09-16 07:39:03 |
| 合計ジャッジ時間 | 5,021 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | AC | 160 ms
41,092 KB |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | AC | 138 ms
35,144 KB |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | AC | 57 ms
20,756 KB |
| testcase_17 | AC | 60 ms
20,708 KB |
| testcase_18 | AC | 57 ms
18,708 KB |
| testcase_19 | AC | 59 ms
20,732 KB |
| testcase_20 | AC | 57 ms
20,748 KB |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
ソースコード
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Program
{
static void Main(string[] args)
{
var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
Console.SetOut(sw);
Solve();
Console.Out.Flush();
}
static void Solve()
{
var N = sc.ReadInt();
var K = sc.ReadInt();
var dij = new Dijkstra(N);
for (int i = 0; i < N - 1; i++)
{
var a = sc.ReadInt();
var b = sc.ReadInt();
a--; b--;
dij.Add(a, b);
dij.Add(b, a);
}
if (K > N)
{
Console.WriteLine(-1);
return;
}
var count = new int[N + 1];
var dist = dij.Calc(0);
for (int i = 0; i < N; i++)
{
var d = dist[i];
count[d]++;
}
var ans = 0;
K--;
for (int i = 1; i < N + 1; i++)
{
for (int j = 0; j < count[i]; j++)
{
if (K > 0) ans += i;
K--;
}
}
Console.WriteLine(ans);
}
class Dijkstra
{
public const long INF = long.MaxValue / 2;
public int V { get; set; }
public int E { get; set; }
public List<Edge>[] G { get; set; }
public Dijkstra(int n)
{
this.V = n;
this.G = new List<Edge>[V];
for (int i = 0; i < V; i++)
{
this.G[i] = new List<Edge>();
}
}
public void Add(int a, int b, long cost = 1)
{
this.G[a].Add(new Edge(b, cost));
this.E++;
}
public long GetMinCost(int start, int goal)
{
var cost = new long[V];
for (int i = 0; i < V; i++) cost[i] = INF;
cost[start] = 0;
var capacity = Math.Max(1, E);
var q = new PriorityQueue<P>(false);
q.Enqueue(new P(start, 0));
while (q.Count > 0)
{
var p = q.Dequeue();
if (p.Cost != cost[p.A]) continue;
foreach (var e in this.G[p.A])
{
if (cost[e.To] > p.Cost + e.Cost)
{
cost[e.To] = p.Cost + e.Cost;
q.Enqueue(new P(e.To, cost[e.To]));
}
}
}
return cost[goal] == long.MaxValue ? -1 : cost[goal];
}
public long[] Calc(int start)
{
var visited = new bool[V];
var cost = new long[V];
for (int i = 0; i < V; i++) cost[i] = INF;
cost[start] = 0;
var capacity = Math.Max(1, E);
var q = new PriorityQueue<P>(false);
q.Enqueue(new P(start, 0));
while (q.Count > 0)
{
var p = q.Dequeue();
visited[p.A] = true;
if (p.Cost != cost[p.A]) continue;
foreach (var e in this.G[p.A])
{
if (cost[e.To] > p.Cost + e.Cost && !visited[e.To])
{
cost[e.To] = p.Cost + e.Cost;
q.Enqueue(new P(e.To, cost[e.To]));
}
}
}
return cost;
}
public struct Edge
{
public int To;
public long Cost;
public Edge(int to, long cost)
{
this.To = to;
this.Cost = cost;
}
}
public struct P : IComparable<P>
{
public int A;
public long Cost;
public P(int a, long cost)
{
this.A = a;
this.Cost = cost;
}
public int CompareTo(P other)
{
return this.Cost.CompareTo(other.Cost);
}
}
class PriorityQueue<T>
{
public int Count;
private int Capacity;
private bool IsMaxHeap;
private T[] Buffer;
private IComparer<T> Cmp;
public PriorityQueue(bool isMaxHeap = true, IComparer<T> cmp = null)
{
Count = 0;
Capacity = 1 << 10;
IsMaxHeap = isMaxHeap;
Buffer = new T[Capacity];
if (cmp != null) Cmp = cmp;
else Cmp = Comparer<T>.Default;
}
public PriorityQueue(int capacity, bool isMaxHeap = true, IComparer<T> cmp = null)
{
Count = 0;
Capacity = Math.Max(16, capacity);
IsMaxHeap = isMaxHeap;
Buffer = new T[Capacity];
if (cmp != null) Cmp = cmp;
else Cmp = Comparer<T>.Default;
}
private void Resize()
{
Capacity <<= 1;
Array.Resize(ref Buffer, Capacity);
}
public void Enqueue(T value)
{
if (Count == Capacity) Resize();
Buffer[Count] = value;
Count++;
UpHeap();
}
public T Dequeue()
{
var res = Buffer[0];
Swap(0, Count - 1);
Count--;
DownHeap();
return res;
}
public T Peek() { return Buffer[0]; }
private void Swap(int i, int j)
{
var tmp = Buffer[i];
Buffer[i] = Buffer[j];
Buffer[j] = tmp;
}
private void UpHeap()
{
var n = this.Count - 1;
while (n != 0)
{
var parent = (n - 1) / 2;
if (Compare(Buffer[n], Buffer[parent]) > 0)
{
Swap(n, parent);
n = parent;
}
else break;
}
}
private void DownHeap()
{
var parent = 0;
while (true)
{
var child = 2 * parent + 1;
if (child > this.Count - 1) break;
if (child < Count - 1 && Compare(Buffer[child], Buffer[child + 1]) < 0)
{
child += 1;
}
if (Compare(Buffer[parent], Buffer[child]) < 0)
{
Swap(parent, child);
parent = child;
}
else break;
}
}
private int Compare(T x, T y)
{
var res = Cmp.Compare(x, y);
if (!IsMaxHeap) res *= -1;
return res;
}
}
}
static Scanner sc = new Scanner();
}
class Scanner
{
string[] S = new string[0];
int Index = 0;
char[] Separators = new char[] { ' ' };
public string Next()
{
if (this.Index < this.S.Length) return this.S[this.Index++];
var line = "";
while (line == "") line = Console.ReadLine();
this.S = line.Split(this.Separators, StringSplitOptions.RemoveEmptyEntries);
if (this.S.Length == 0) return this.Next();
this.Index = 0;
return this.S[this.Index++];
}
public string ReadStr()
{
return this.Next();
}
public char ReadChar()
{
return this.Next()[0];
}
public int ReadInt()
{
return int.Parse(this.Next());
}
public uint ReadUInt()
{
return uint.Parse(this.Next());
}
public long ReadLong()
{
return long.Parse(this.Next());
}
public double ReadDouble()
{
return double.Parse(this.Next());
}
public Tuple<int, int> ReadTup(int add = 0)
{
return Tuple.Create(this.ReadInt() + add, this.ReadInt() + add);
}
public Tuple<long, long> ReadTupLong(int add = 0)
{
return Tuple.Create(this.ReadLong() + add, this.ReadLong() + add);
}
public Tuple<int, int, int> ReadTup3(int add = 0)
{
return Tuple.Create(this.ReadInt() + add, this.ReadInt() + add, this.ReadInt() + add);
}
public Tuple<int, int, int, int> ReadTup4(int add = 0)
{
return Tuple.Create(this.ReadInt() + add, this.ReadInt() + add, this.ReadInt() + add, this.ReadInt() + add);
}
public int[] ReadIntArray(int n)
{
var array = new int[n];
for (int i = 0; i < array.Length; i++)
{
array[i] = this.ReadInt();
}
return array;
}
public long[] ReadLongArray(int n)
{
var array = new long[n];
for (int i = 0; i < array.Length; i++)
{
array[i] = this.ReadLong();
}
return array;
}
public double[] ReadDoubleArray(int n)
{
var array = new double[n];
for (int i = 0; i < array.Length; i++)
{
array[i] = this.ReadDouble();
}
return array;
}
public char[] ReadCharArray(int n)
{
var array = new char[n];
for (int i = 0; i < array.Length; i++)
{
array[i] = this.ReadChar();
}
return array;
}
public string[] ReadStrArray(int n)
{
var array = new string[n];
for (int i = 0; i < array.Length; i++)
{
array[i] = this.ReadStr();
}
return array;
}
public Tuple<long, long>[] ReadTupLongArray(int n, int add = 0)
{
var array = new Tuple<long, long>[n];
for (int i = 0; i < n; i++)
{
array[i] = this.ReadTupLong(add);
}
return array;
}
public Tuple<int, int>[] ReadTupArray(int n, int add = 0)
{
var array = new Tuple<int, int>[n];
for (int i = 0; i < n; i++)
{
array[i] = this.ReadTup(add);
}
return array;
}
public Tuple<int, int, int>[] ReadTup3Array(int n, int add = 0)
{
var array = new Tuple<int, int, int>[n];
for (int i = 0; i < n; i++)
{
array[i] = this.ReadTup3(add);
}
return array;
}
public Tuple<int, int, int, int>[] ReadTup4Array(int n, int add = 0)
{
var array = new Tuple<int, int, int, int>[n];
for (int i = 0; i < n; i++)
{
array[i] = this.ReadTup4(add);
}
return array;
}
}