結果
問題 | No.340 雪の足跡 |
ユーザー | sdfgsjhafs |
提出日時 | 2020-02-04 21:52:47 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 9,849 bytes |
コンパイル時間 | 1,010 ms |
コンパイル使用メモリ | 119,148 KB |
実行使用メモリ | 72,084 KB |
最終ジャッジ日時 | 2024-09-21 07:45:39 |
合計ジャッジ時間 | 5,843 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 36 ms
35,148 KB |
testcase_01 | AC | 34 ms
28,672 KB |
testcase_02 | AC | 30 ms
28,152 KB |
testcase_03 | AC | 35 ms
26,928 KB |
testcase_04 | AC | 35 ms
26,800 KB |
testcase_05 | AC | 30 ms
26,148 KB |
testcase_06 | AC | 34 ms
26,548 KB |
testcase_07 | AC | 35 ms
26,624 KB |
testcase_08 | AC | 36 ms
26,416 KB |
testcase_09 | AC | 34 ms
26,732 KB |
testcase_10 | AC | 35 ms
26,740 KB |
testcase_11 | AC | 66 ms
31,232 KB |
testcase_12 | AC | 58 ms
32,140 KB |
testcase_13 | AC | 83 ms
32,664 KB |
testcase_14 | TLE | - |
testcase_15 | TLE | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections.Generic; using System.Linq; using System.Text; // using System.Numerics; using System.Runtime.CompilerServices; using System.Diagnostics; using ll=System.Int64; using static Contest_D.Lib_IO; using static Contest_D.Lib_Minifunc; public static class Contest_D { public static void Main() { checked{ int w,h,n,dum; Lib_IO.rm(out w,out h, out n); int[][] b = new int[n][]; for (int i = 0; i < n; i++) { rm(out dum); ra(out b[i]); } HashSet<string> v = new HashSet<string>(); Dictionary<int,int>[] graph = new Dictionary<int, int>[h*w]; for (int i = 0; i < h*w; i++) { graph[i] = new Dictionary<int, int>(); } foreach (var e in b) { for (int i = 0; i < e.Length-1; i++) { int x1 = e[i]%w; int y1 = e[i]/w; int x2 = e[i+1]%w; int y2 = e[i+1]/w; if(x1==x2){ if(y1<y2){ for (int k = y1; k < y2; k++) { string ky = (k*w+x1).ToString()+","+((k+1)*w+x1).ToString(); if(!v.Contains(ky)){ v.Add(ky); graph[k*w+x1][(k+1)*w+x1] = 1; graph[(k+1)*w+x1][k*w+x1] = 1; } } }else{ for (int k = y2; k < y1; k++) { string ky = (k*w+x1).ToString()+","+((k+1)*w+x1).ToString(); if(!v.Contains(ky)){ v.Add(ky); graph[k*w+x1][(k+1)*w+x1] = 1; graph[(k+1)*w+x1][k*w+x1] = 1; } } } }else{ if(x1<x2){ for (int k = x1; k < x2; k++) { string ky = (y1*w+k).ToString()+","+(y1*w+k+1).ToString(); if(!v.Contains(ky)){ v.Add(ky); graph[y1*w+k][y1*w+k+1] = 1; graph[y1*w+k+1][y1*w+k] = 1; } } }else{ for (int k = x2; k < x1; k++) { string ky = (y1*w+k).ToString()+","+(y1*w+k+1).ToString(); if(!v.Contains(ky)){ v.Add(ky); graph[y1*w+k][y1*w+k+1] = 1; graph[y1*w+k+1][y1*w+k] = 1; } } } } } } var rt = (int)Search(2,h*w,graph,0,0,h*w-1); Lib_IO.wm(rt==-1?"Odekakedekinai..":rt.ToString()); } } public static object Search(long stype, long N, IList<Dictionary<int,int>> graph, int startidx, int depth,int goal){ var que = new ModQue<P<KeyValuePair<int,int>,int>>(stype); que.In(new P<KeyValuePair<int,int>, int>(new KeyValuePair<int, int>(startidx,int.MaxValue),depth)); // 第2引数は次のノードに渡す情報を代入(コストの和など) var visited = new bool[N]; while(0<que.Count()){ var cur = que.Out(); if(visited[cur.A.Key]) continue; visited[cur.A.Key]=true; var info = cur.B; if(cur.A.Key==goal) return info; foreach (var e in graph[cur.A.Key]) { que.In(new P<KeyValuePair<int,int>, int>(e,info+1)); } } return -1; } public class ModQue<T>{ readonly public Action Clear; readonly public Action<T> In; readonly public Func<T> Out, Peek; readonly public Func<int> Count; public ModQue(long type){ if(type==1) { var S = new Stack<T>(); Clear = S.Clear; Peek = S.Peek; Count = () => S.Count; In = S.Push; Out = S.Pop; } if(type==2) { var Q = new Queue<T>(); Clear = Q.Clear; Peek = Q.Peek; Count = () => Q.Count; In = Q.Enqueue; Out = Q.Dequeue; } } } #region BaseModule public static class Lib_Minifunc{ [MethodImpl(256)] public static void swap1<T>(ref T a, ref T b) { T t = a; a = b; b = t; } [MethodImpl(256)] public static void swap2<T>(ref T a, ref T b) where T : IComparable { if (a.CompareTo(b)==1) swap1(ref a, ref b); } // b の方が小さければ交換 [MethodImpl(256)] public static bool chmin<T>(ref T a, T b) where T : IComparable { if (a.CompareTo(b)== 1) { a = b; return true; } return false; } // b の方が小さければ a を更新 [MethodImpl(256)] public static bool chmax<T>(ref T a, T b) where T : IComparable { if (a.CompareTo(b)==-1) { a = b; return true; } return false; } // b の方が大きければ a を更新 [MethodImpl(256)] public static bool inside(long i, long n) => (0<=i&&i<n); [MethodImpl(256)] public static bool inside(long x, long y, long w, long h) => (inside(x,w)&&inside(y,h)); [MethodImpl(256)] public static T min<T>(params T[] a) where T : IComparable => a.Min(); [MethodImpl(256)] public static T max<T>(params T[] a) where T : IComparable => a.Max(); [MethodImpl(256)] public static long mod(long a, long m=MOD1) { var v = a%m; return (v<0?v+m:v); } [MethodImpl(256)] public static long ceiling(long a, long b) => (a%b==0?a/b:a/b+1); // 整数商の切り上げ [MethodImpl(256)] public static P<T,U> initp<T,U>(T a,U b) => new P<T,U>(a,b); [MethodImpl(256)] public static P<T,U,V> initp<T,U,V>(T a,U b,V c) => new P<T,U,V>(a,b,c); [MethodImpl(256)] public static P<T,U,V,W> initp<T,U,V,W>(T a,U b,V c,W d) => new P<T,U,V,W>(a,b,c,d); [MethodImpl(256)] public static bool initd<T,U>(Dictionary<T,U> d, T k) { if(d.ContainsKey(k)) { return false; } else { d[k] = default(U); return true; } } public static T[][] initm<T>(long len1,long len2,T val) where T : struct { var m = new T[len1][]; for (int i=0;i<m.Length;i++) m[i] = Enumerable.Repeat(val,(int)len2).ToArray(); return m; } public static T[][][] initm<T>(long len1,long len2,long len3,T val) where T : struct { var m = new T[len1][][]; for (int i=0;i<m.Length;i++) m[i] = initm(len2,len3,val); return m; } public const long MOD1 = 1000000007; // 10^9+7 public const double EPS1 = 1e-8; public const long INF1 = 1000000000000000; // 10^15 } public struct P<T,U> { public T A; public U B; public P(T a,U b) { A = a; B = b; } public static implicit operator KeyValuePair<T,U>(P<T,U> a) => new KeyValuePair<T,U>(a.A,a.B); public static implicit operator P<T,U>(KeyValuePair<T,U> a) => new P<T,U>(a.Key,a.Value); } public struct P<T,U,V> { public T A; public U B; public V C; public P(T a,U b,V c) { A = a; B = b; C = c; } } public struct P<T,U,V,W> { public T A; public U B; public V C; public W D; public P(T a,U b,V c,W d) { A = a; B = b; C = c; D = d; } } public static class Lib_IO { class Prt : System.IO.StreamWriter { public override IFormatProvider FormatProvider { get { return System.Globalization.CultureInfo.InvariantCulture; } } public Prt(System.IO.Stream s) : base(s,new UTF8Encoding(false,true)) {} public Prt(System.IO.Stream s,Encoding e) : base(s,e) {} } static Prt sw = new Prt(Console.OpenStandardOutput()); static char[] sp = new char[] {' '}; [MethodImpl(256)] static bool eq<T,U>() => typeof(T).Equals(typeof(U)); [MethodImpl(256)] static T ct<T,U>(U a) => (T)Convert.ChangeType(a,typeof(T)); [MethodImpl(256)] static T cv<T>(string s) => eq<T,int>() ? ct<T,int>(int.Parse(s)) : eq<T,long>() ? ct<T,long>(long.Parse(s)) : eq<T,double>() ? ct<T,double>(double.Parse(s,System.Globalization.CultureInfo.InvariantCulture)) : eq<T,char>() ? ct<T,char>(s[0]) : ct<T,string>(s); public static string[] rm<T>(out T a) { var z = Console.ReadLine().Split(sp,StringSplitOptions.RemoveEmptyEntries); a = cv<T>(z[0]); return z; } public static string[] rm<T,U>(out T a,out U b) { var z = rm<T>(out a); b = cv<U>(z[1]); return z; } public static string[] rm<T,U,V>(out T a,out U b,out V c) { var z = rm<T,U>(out a,out b); c = cv<V>(z[2]); return z; } public static string[] rm<T,U,V,W>(out T a,out U b,out V c,out W d) { var z = rm<T,U,V>(out a,out b,out c); d = cv<W>(z[3]); return z; } public static string[] rm<T,U,V,W,X>(out T a,out U b,out V c,out W d,out X e) { var z = rm<T,U,V,W>(out a,out b,out c,out d); e = cv<X>(z[4]); return z; } public static string[] rm<T,U,V,W,X,Y>(out T a,out U b,out V c,out W d,out X e,out Y f) { var z = rm<T,U,V,W,X>(out a,out b,out c,out d,out e); f = cv<Y>(z[5]); return z; } public static string[] ra<T>(out T[] a) { var z = Console.ReadLine().Split(sp,StringSplitOptions.RemoveEmptyEntries); a = z.Select(cv<T>).ToArray(); return z; } public static string[][] rl<T>(long n,out T[] a) { a = new T[n]; var y = new string[n][]; for(int i=0;i<n;i++) y[i] = rm(out a[i]); return y; } public static string[][] rl<T,U>(long n,out P<T,U>[] a) { a = new P<T,U>[n]; var y = new string[n][]; for(int i=0;i<n;i++) { T o; U p; y[i] = rm(out o,out p); a[i] = new P<T,U>(o,p); } return y; } public static string[][] rl<T,U,V>(long n,out P<T,U,V>[] a) { a = new P<T,U,V>[n]; var y = new string[n][]; for(int i=0;i<n;i++) { T o; U p; V q; y[i] = rm(out o,out p,out q); a[i] = new P<T,U,V>(o,p,q); } return y; } public static string[][] rl<T,U,V,W>(long n,out P<T,U,V,W>[] a) { a = new P<T,U,V,W>[n]; var y = new string[n][]; for(int i=0;i<n;i++) { T o; U p; V q; W r; y[i] = rm(out o,out p,out q,out r); a[i] = new P<T,U,V,W>(o,p,q,r); } return y; } public static string[][] rx<T>(long n,out T[][] a) { a = new T[n][]; var y = new string[n][]; for(int i=0;i<n;i++) y[i] = ra(out a[i]); return y; } static void wwp(Action act){ sw.AutoFlush = false; Console.SetOut(sw); act(); Console.Out.Flush(); sw.AutoFlush = true; Console.SetOut(sw); } [MethodImpl(256)] static string wfm(Type t) =>t.Equals(typeof(double)) ? "{0:F10}" : "{0}"; public static void wm(params object[] a) { wwp(()=>{ for(int i=0;i<a.Length;i++) { var f = wfm(a[i].GetType()) + ((i<a.Length-1) ? " " : Environment.NewLine); Console.Write(f,a[i]); } }); } public static void wa<T>(IList<T> a) { wwp(()=>{ var f = wfm(typeof(T)); var g = f + " "; var h = f + Environment.NewLine; for(int i=0;i<a.Count;i++) Console.Write(((i<a.Count-1) ? g : h),a[i]); }); } public static void wl<T>(IList<T> a) { wwp(()=>{ var f = wfm(typeof(T)) + Environment.NewLine; foreach(T x in a) Console.Write(f,x); }); } } #endregion }