AtCoder Regular Contest 030

Submission #1353358

Source codeソースコード

//#pragma warning disable
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System;
using System.Numerics;
using System.Threading.Tasks;
using static System.Math;
using static System.Console;
class E { static void Main() => new K(); }
class K
{
	int F() => int.Parse(ReadLine());
	long FL() => int.Parse(ReadLine());
	int[] G() => ReadLine().Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();
	long[] GL() => ReadLine().Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries).Select(long.Parse).ToArray();
	public const int MOD = 1000000007;
	public K()
	{
		//SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		//Out.Flush();
	}
	int V, E, k, M;
	char[] c;
	int[] which;
	List<int>[] es, res, fs;
	string[] strs;
	string[,] dp;
	void Solve()
	{
		var I = G();
		V = I[0];
		E = I[1];
		k = I[2];
		c = Console.ReadLine().Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries).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();
		dp = new string[M, k + 1];
		for (var u = M - 1; u >= 0; u--)
		{
			var len = strs[u].Length;
			dp[u, 0] = "";
			for (var n = 1; n <= k; n++)
			{
				if (n <= len) dp[u, n] = strs[u].Substring(0, n);
				if (fs[u].Count != 0)
				{
					for (var m = 1; m <= n && m <= len; m++)
					{
						var best = dp[fs[u][0], n - m];
						foreach (var v in fs[u].Skip(1)) if (Compare(best, dp[v, n - m]) > 0) best = dp[v, n - m];
						var tmp = strs[u].Substring(0, m) + best;
						if (Compare(dp[u, n], tmp) > 0) dp[u, n] = tmp;
					}
				}
			}
		}
		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);
	}
	public void StronglyConnectedComponents()
	{
		var mark = new bool[V];
		var stack = new Stack<int>();
		Action<int> dfs = null;
		dfs = v =>
		{
			mark[v] = true;
			foreach (var w in es[v]) if (!mark[w]) dfs(w);
			stack.Push(v);
		};
		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];
		Action<int, HashSet<int>> rdfs = null;
		rdfs = (v, set) =>
		{
			set.Add(v);
			mark[v] = true;
			foreach (var w in res[v]) if (!mark[w]) rdfs(w, set);
		};
		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 List<int>[M];
		var tmp = new List<char>[M];
		for (var v = 0; v < M; v++) fs[v] = new List<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]);
		strs = new string[M];
		for (var v = 0; v < M; v++)
		{
			tmp[v].Sort();
			strs[v] = new string(tmp[v].ToArray());
		}
		for (var v = 0; v < V; v++) foreach (var w in es[v])
			{
				int a = which[v], b = which[w];
				if (a != b) fs[a].Add(b);
			}
	}
}

Submission

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

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 0 / 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 48 ms 10848 KB
subtask0_sample_02.txt WA
subtask0_sample_03.txt AC 37 ms 11872 KB
subtask0_sample_04.txt AC 33 ms 11744 KB
subtask1_manual01.txt AC 37 ms 11872 KB
subtask1_manual02.txt AC 37 ms 11872 KB
subtask1_manual03.txt WA
subtask1_manual04.txt WA
subtask1_manual05.txt WA
subtask1_manual06.txt WA
subtask1_manual07.txt WA
subtask1_manual08.txt WA
subtask1_random01.txt WA
subtask1_random02.txt WA
subtask1_random03.txt WA
subtask1_random04.txt WA
subtask1_random05.txt AC 38 ms 9824 KB
subtask1_special01.txt AC 34 ms 11744 KB
subtask1_special02.txt WA
subtask1_special03.txt WA
subtask1_special04.txt WA
subtask1_special05.txt WA
subtask1_special06.txt WA
subtask1_special07.txt WA
subtask1_special08.txt WA
subtask1_special09.txt WA
subtask1_special10.txt WA
subtask1_special11.txt WA
subtask1_special12.txt WA
subtask1_special13.txt WA
subtask1_special14.txt AC 34 ms 11860 KB
subtask1_special15.txt WA