Submission #1353363


Source Code Expand

//#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;
	// dp[i,n] = i番目のSCCから初めてn文字とる
	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;
					}
				}
				if (dp[u, n] != null && dp[u, n].Length != n) dp[u, n] = null;
				//Console.WriteLine("dp[{0}, {1}] = {2}", u, n, dp[u, n]);
			}
		}
		//Console.WriteLine("M = {0}", M);
		//for (var i = 0; i < V; i++) Console.WriteLine("f[{0}] = {1}", i, which[i]);
		//for (var i = 0; i < M; i++) foreach (var w in fs[i]) Console.WriteLine("{0} -> {1}", i, w);
		//for (var i = 0; i < M; i++) Console.WriteLine("S[{0}] = {1}", i, strs[i]);
		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");
	}
	// null is max
	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 Info

Submission Time
Task C - 有向グラフ
User selpo
Language C# (Mono 4.6.2.0)
Score 0
Code Size 4080 Byte
Status WA
Exec Time 134 ms
Memory 27604 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 4
AC × 15
WA × 17
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt
All 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
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 49 ms 12512 KB
subtask0_sample_02.txt AC 38 ms 9824 KB
subtask0_sample_03.txt AC 38 ms 11872 KB
subtask0_sample_04.txt AC 35 ms 11860 KB
subtask1_manual01.txt AC 37 ms 9940 KB
subtask1_manual02.txt AC 38 ms 11872 KB
subtask1_manual03.txt AC 38 ms 11872 KB
subtask1_manual04.txt WA 38 ms 11872 KB
subtask1_manual05.txt WA 38 ms 11864 KB
subtask1_manual06.txt AC 38 ms 11872 KB
subtask1_manual07.txt AC 38 ms 11872 KB
subtask1_manual08.txt AC 38 ms 9824 KB
subtask1_random01.txt WA 65 ms 11956 KB
subtask1_random02.txt WA 43 ms 11872 KB
subtask1_random03.txt WA 134 ms 18188 KB
subtask1_random04.txt WA 65 ms 11964 KB
subtask1_random05.txt AC 39 ms 11872 KB
subtask1_special01.txt AC 35 ms 9696 KB
subtask1_special02.txt WA 39 ms 9952 KB
subtask1_special03.txt WA 49 ms 18268 KB
subtask1_special04.txt WA 61 ms 23892 KB
subtask1_special05.txt AC 66 ms 23508 KB
subtask1_special06.txt WA 93 ms 16476 KB
subtask1_special07.txt WA 70 ms 16224 KB
subtask1_special08.txt WA 90 ms 14428 KB
subtask1_special09.txt WA 93 ms 18524 KB
subtask1_special10.txt WA 93 ms 20572 KB
subtask1_special11.txt WA 95 ms 18392 KB
subtask1_special12.txt WA 92 ms 16224 KB
subtask1_special13.txt WA 95 ms 18272 KB
subtask1_special14.txt AC 34 ms 11744 KB
subtask1_special15.txt AC 68 ms 27604 KB