AtCoder Regular Contest 030

Submission #1353413

Source codeソースコード

using System.Collections.Generic;
using System.Linq;
using System;
using static System.Math;
using static System.Console;
class E { static void Main() => new K(); }
class K
{
	int[] G() => ReadLine().Split().Select(int.Parse).ToArray();
	int V, E, k, M;
	char[] c;
	int[] which;
	List<int>[] es, res;
	HashSet<int>[] fs;
	string[] s;
	public K()
	{
		var I = G();
		V = I[0];
		E = I[1];
		k = I[2];
		c = Console.ReadLine().Split().Select(s => s[0]).ToArray();
		es = new List<int>[V];
		res = new List<int>[V];
		for (var i = 0; i < V; i++) es[i] = new List<int>();
		for (var i = 0; i < V; i++) res[i] = new List<int>();
		for (var i = 0; i < E; i++)
		{
			I = G();
			int a = I[0] - 1, b = I[1] - 1;
			es[a].Add(b);
			res[b].Add(a);
		}
		StronglyConnectedComponents();
		var dp = new string[M, k + 1];
		var ls = new int[M];
		for (var u = M - 1; u >= 0; u--)
		{
			foreach (var v in fs[u]) ls[u] = Max(ls[u], ls[v]);
			ls[u] += s[u].Length;
		}
		for (var u = M - 1; u >= 0; u--)
		{
			var len = s[u].Length;
			dp[u, 0] = "";
			for (var n = 1; n <= k && n <= ls[u]; n++)
			{
				if (n <= len) dp[u, n] = s[u].Substring(0, n);
				if (fs[u].Count > 0)
				{
					for (var m = Max(0, n + len - ls[u]); m <= n && m <= len; m++)
					{
						string best = null;
						foreach (var v in fs[u]) if (Compare(best, dp[v, n - m]) > 0) best = dp[v, n - m];
						var tmp = s[u].Substring(0, m) + best;
						if (Compare(dp[u, n], tmp) > 0) dp[u, n] = tmp;
					}
				}
				if (dp[u, n] != null && dp[u, n].Length != n) dp[u, n] = null;
			}
		}
		string min = null;
		for (var i = 0; i < M; i++) if (Compare(min, dp[i, k]) > 0) min = dp[i, k];
		Console.WriteLine(min ?? "-1");
	}
	int Compare(string a, string b)
	{
		if (a == b) return 0;
		if (a == null) return 1;
		if (b == null) return -1;
		return a.CompareTo(b);
	}
	bool[] mark;
	Stack<int> stack;
	void DFS(int v)
	{
		mark[v] = true;
		foreach (var w in es[v]) if (!mark[w]) DFS(w);
		stack.Push(v);
	}
	void RDFS(int v, HashSet<int> set)
	{
		set.Add(v);
		mark[v] = true;
		foreach (var w in res[v]) if (!mark[w]) RDFS(w, set);
	}
	public void StronglyConnectedComponents()
	{
		mark = new bool[V];
		stack = new Stack<int>();
		for (var v = 0; v < V; v++) if (!mark[v]) DFS(v);
		var scc = new List<HashSet<int>>();
		mark = new bool[V];
		which = new int[V];
		while (stack.Count > 0)
		{
			var v = stack.Pop();
			if (mark[v]) continue;
			var set = new HashSet<int>();
			RDFS(v, set);
			scc.Add(set);
			foreach (var w in set) which[w] = M;
			M++;
		}
		fs = new HashSet<int>[M];
		var tmp = new List<char>[M];
		for (var v = 0; v < M; v++) fs[v] = new HashSet<int>();
		for (var v = 0; v < M; v++) tmp[v] = new List<char>();
		for (var v = 0; v < V; v++) tmp[which[v]].Add(c[v]);
		s = new string[M];
		for (var v = 0; v < M; v++)
		{
			tmp[v].Sort();
			s[v] = new string(tmp[v].ToArray());
		}
		for (var v = 0; v < V; v++) foreach (var w in es[v]) fs[which[v]].Add(which[w]);
		for (var v = 0; v < M; v++) fs[v].Remove(v);
	}
}

Submission

Task問題 C - 有向グラフ
User nameユーザ名 selpo
Created time投稿日時
Language言語 C# (Mono 4.6.2.0)
Status状態 AC
Score得点 100
Source lengthソースコード長 3126 Byte
File nameファイル名
Exec time実行時間 97 ms
Memory usageメモリ使用量 19420 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_sample_01.txt,subtask0_sample_02.txt,subtask0_sample_03.txt,subtask0_sample_04.txt
All 100 / 100 subtask0_sample_01.txt,subtask0_sample_02.txt,subtask0_sample_03.txt,subtask0_sample_04.txt,subtask1_manual01.txt,subtask1_manual02.txt,subtask1_manual03.txt,subtask1_manual04.txt,subtask1_manual05.txt,subtask1_manual06.txt,subtask1_manual07.txt,subtask1_manual08.txt,subtask1_random01.txt,subtask1_random02.txt,subtask1_random03.txt,subtask1_random04.txt,subtask1_random05.txt,subtask1_special01.txt,subtask1_special02.txt,subtask1_special03.txt,subtask1_special04.txt,subtask1_special05.txt,subtask1_special06.txt,subtask1_special07.txt,subtask1_special08.txt,subtask1_special09.txt,subtask1_special10.txt,subtask1_special11.txt,subtask1_special12.txt,subtask1_special13.txt,subtask1_special14.txt,subtask1_special15.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask0_sample_01.txt AC 45 ms 14804 KB
subtask0_sample_02.txt AC 36 ms 11872 KB
subtask0_sample_03.txt AC 37 ms 11872 KB
subtask0_sample_04.txt AC 34 ms 11860 KB
subtask1_manual01.txt AC 36 ms 11988 KB
subtask1_manual02.txt AC 36 ms 11872 KB
subtask1_manual03.txt AC 36 ms 11872 KB
subtask1_manual04.txt AC 36 ms 13920 KB
subtask1_manual05.txt AC 36 ms 11872 KB
subtask1_manual06.txt AC 36 ms 11872 KB
subtask1_manual07.txt AC 36 ms 11872 KB
subtask1_manual08.txt AC 36 ms 11872 KB
subtask1_random01.txt AC 42 ms 14124 KB
subtask1_random02.txt AC 39 ms 13920 KB
subtask1_random03.txt AC 43 ms 12000 KB
subtask1_random04.txt AC 39 ms 9908 KB
subtask1_random05.txt AC 38 ms 11988 KB
subtask1_special01.txt AC 35 ms 11744 KB
subtask1_special02.txt AC 39 ms 13920 KB
subtask1_special03.txt AC 55 ms 14176 KB
subtask1_special04.txt AC 68 ms 16988 KB
subtask1_special05.txt AC 72 ms 19420 KB
subtask1_special06.txt AC 95 ms 18524 KB
subtask1_special07.txt AC 79 ms 19296 KB
subtask1_special08.txt AC 94 ms 16476 KB
subtask1_special09.txt AC 97 ms 18524 KB
subtask1_special10.txt AC 97 ms 16476 KB
subtask1_special11.txt AC 95 ms 15836 KB
subtask1_special12.txt AC 95 ms 17628 KB
subtask1_special13.txt AC 95 ms 15320 KB
subtask1_special14.txt AC 34 ms 11744 KB
subtask1_special15.txt AC 52 ms 18784 KB