Submission #1303486


Source Code Expand

using System.Collections.Generic;
using System.Linq;
using System;
struct Pair
{
	public int u, d;
	public Pair(int u, int d = 0)
	{
		this.u = u;
		this.d = d;
	}
}
class E { static void Main() { new J(); } }
class J
{
	const int INF = 1000000007;
	int V, R, T;
	List<Pair>[] es;
	long s;
	public J()
	{
		var I = G();
		V = I[0];
		int E = I[1]; R = I[2]; T = I[3];
		es = new List<Pair>[V];
		var deg = new int[V];
		for (var i = 0; i < V; i++) es[i] = new List<Pair>();
		for (var e = 0; e < E; e++)
		{
			I = G();
			int a = I[0] - 1, b = I[1] - 1, c = I[2];
			es[a].Add(new Pair(b, c));
			es[b].Add(new Pair(a, c));
			deg[a]++; deg[b]++;
		}
		var hoge = new List<int>(V);
		for (var i = 0; i < V; i++) hoge.Add(i);
		hoge.Sort((x, y) => deg[x].CompareTo(deg[y]));
		lands = hoge.Take(6).ToArray();
		island = new HashSet<int>(lands);
		foreach (var x in lands.Take(1))
		{
			var d = DijkstraFrom0(x);
			Estimate0(d);
			Calc(d);
		}
		foreach (var x in lands.Skip(1))
		{
			var d = DijkstraFrom(x);
			Estimate(d);
			Calc(d);
		}
		for (var u = 0; u < V; u++) if (!island.Contains(u)) Calc(DijkstraFrom(u));
		Console.WriteLine(s);
		//for (var u = 0; u < V; u++) for (var v = 0; v < V; v++) Console.WriteLine("d[{0}, {1}] = {2}", u, v, est[u, v]);
	}
	void Estimate0(int[] d)
	{
		est = new int[V, V];
		for (var u = 0; u < V; u++) for (var v = 0; v < V; v++) est[u, v] = d[u] + d[v];
	}
	void Estimate(int[] d)
	{
		for (var u = 0; u < V; u++) for (var v = 0; v < V; v++) est[u, v] = Math.Min(est[u, v], d[u] + d[v]);
	}
	void Calc(int[] d)
	{
		Array.Sort(d);
		var i = 1;
		for (var x = 1; x < V; x++)
		{
			var t = R * d[x] / T;
			while (i < V && t >= d[i]) i++;
			if (i == V) return;
			s += V - i;
			if (i <= x) s--;
		}
	}
	PriorityQueue q = new PriorityQueue();
	int[] lands;
	HashSet<int> island;
	int[,] est;
	int[] DijkstraFrom0(int u)
	{
		var d = new int[V];
		for (var i = 0; i < V; i++) d[i] = INF;
		q.Enqueue(new Pair(u, d[u] = 0));
		while (q.Count > 0)
		{
			var p = q.Dequeue();
			var v = p.u;
			if (d[v] < p.d) continue;
			foreach (var e in es[v])
			{
				var tmp = d[v] + e.d;
				if (d[e.u] > tmp) q.Enqueue(new Pair(e.u, d[e.u] = tmp));
			}
		}
		return d;
	}
	int[] DijkstraFrom(int u)
	{
		var d = new int[V];
		for (var i = 0; i < V; i++) d[i] = INF;
		q.Enqueue(new Pair(u, d[u] = 0));
		while (q.Count > 0)
		{
			var p = q.Dequeue();
			var v = p.u;
			if (d[v] < p.d) continue;
			foreach (var e in es[v])
			{
				var tmp = d[v] + e.d;
				if (d[e.u] > tmp && est[u, e.u] >= tmp) q.Enqueue(new Pair(e.u, d[e.u] = tmp));
			}
		}
		for (var i = u + 1; i < V; i++) est[i, u] = d[i];
		return d;
	}
	List<int> G()
	{
		var line = Console.ReadLine();
		var ans = new List<int>();
		var n = 0;
		foreach (var c in line)
		{
			if (c == ' ')
			{
				ans.Add(n);
				n = 0;
			}
			else n = 10 * n + (c - '0');
		}
		ans.Add(n);
		return ans;
	}
}
class PriorityQueue
{
	List<Pair> list = new List<Pair>(10000);
	public int Count;
	public void Enqueue(Pair x)
	{
		var pos = Count++;
		list.Add(x);
		while (pos > 0)
		{
			var p = (pos - 1) / 2;
			if (list[p].d <= x.d) break;
			list[pos] = list[p];
			pos = p;
		}
		list[pos] = x;
	}
	public Pair Dequeue()
	{
		var value = list[0];
		var x = list[--Count];
		list.RemoveAt(Count);
		if (Count == 0) return value;
		var pos = 0;
		while (pos * 2 + 1 < Count)
		{
			var a = 2 * pos + 1;
			var b = 2 * pos + 2;
			if (b < Count && list[b].d < list[a].d) a = b;
			if (list[a].d >= x.d) break;
			list[pos] = list[a];
			pos = a;
		}
		list[pos] = x;
		return value;
	}
}

Submission Info

Submission Time
Task C - ウサギとカメ
User selpo
Language C# (Mono 4.6.2.0)
Score 100
Code Size 3750 Byte
Status AC
Exec Time 3026 ms
Memory 58456 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 18
Set Name Test Cases
Sample subtask0_sample-01.txt, subtask0_sample-02.txt
All subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt
Case Name Status Exec Time Memory
subtask0_sample-01.txt AC 31 ms 11644 KB
subtask0_sample-02.txt AC 30 ms 11644 KB
subtask1_01.txt AC 31 ms 13664 KB
subtask1_02.txt AC 30 ms 9568 KB
subtask1_03.txt AC 31 ms 11644 KB
subtask1_04.txt AC 30 ms 9568 KB
subtask1_05.txt AC 44 ms 11744 KB
subtask1_06.txt AC 47 ms 11744 KB
subtask1_07.txt AC 85 ms 9952 KB
subtask1_08.txt AC 112 ms 10208 KB
subtask1_09.txt AC 834 ms 24416 KB
subtask1_10.txt AC 859 ms 23520 KB
subtask1_11.txt AC 345 ms 16096 KB
subtask1_12.txt AC 2851 ms 58456 KB
subtask1_13.txt AC 2833 ms 54360 KB
subtask1_14.txt AC 3005 ms 58456 KB
subtask1_15.txt AC 1951 ms 43096 KB
subtask1_16.txt AC 3026 ms 56408 KB