Submission #20644324


Source Code Expand

Copy
using AtCoder;
using AtCoder.Internal;
using Kzrnm.Competitive;
using Kzrnm.Competitive.IO;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Linq.Expressions;
using System.Runtime.CompilerServices;
using System.Text;
using static Kzrnm.Competitive.Global;
using static System.Math;
partial class Program
{
    partial void WriteBool(bool b) => cw.WriteLine(b ? "Yes" : "No");
    bool __ManyTestCases() => false;
    [MethodImpl(MethodImplOptions.AggressiveOptimization)]
    private object Calc()
    {
        int N = cr;
        int M = cr;
        int V = cr.Int0;
        X = cr;
        Y = cr;
        int W = cr.Int0;
        var gb = new WULongGraphBuilder(N, false);
        for (int m = 0; m < M; m++) gb.Add(Ix(cr.Int0), Ix(cr.Int0), cr.ULong);

        X = Abs(X);
        Y = Abs(Y);
        if (X < Y) (X, Y) = (Y, X);

        graph = gb.ToGraph();
        var starts = graph.Dijkstra(V);
        var goals = graph.Dijkstra(W);
        Array.Copy(graph.Dijkstra(0), lens[0], 4);
        Array.Copy(graph.Dijkstra(1), lens[1], 4);
        Array.Copy(graph.Dijkstra(2), lens[2], 4);
        Array.Copy(graph.Dijkstra(3), lens[3], 4);
        {
            var pq = PriorityQueue.CreateDictionary<ulong, (int i, int j, int c)>();
            for (int c = 0; c < 4; c++)
                if (r[DELTA][DELTA][c].UpdateMin(starts[c]))
                    pq.Add(starts[c], (DELTA, DELTA, c));
            while (pq.Count > 0)
            {
                var (x, y, c) = pq.Peek.Value;
                if (r[x][y][c] < pq.Dequeue().Key) continue;

                for (int cc = 0; cc < 4; cc++)
                    if (lens[c][cc] < ulong.MaxValue && r[x][y][cc].UpdateMin(r[x][y][c] + lens[c][cc]))
                        pq.Add(r[x][y][cc], (x, y, cc));

                var (nx, ny, nc) = c switch
                {
                    0 => (x + 1, y, 2),
                    1 => (x, y + 1, 3),
                    2 => (x - 1, y, 0),
                    _ => (x, y - 1, 1),
                };
                if ((uint)nx <= 2 * DELTA && (uint)ny <= 2 * DELTA && r[nx][ny][nc].UpdateMin(r[x][y][c]))
                    pq.Add(r[nx][ny][nc], (nx, ny, nc));
            }
        }
        ulong res = ulong.MaxValue;
        if (X == 0 && Y == 0) res.UpdateMin(starts[W]);
        for (int c = 0; c < 4; c++)
            checked
            {
                try
                {
                    res.UpdateMin(Calc(X, Y, c) + goals[c]);
                }
                catch { }
            }
        return (long)res;
    }
    ulong Calc(int x, int y, int c)
    {
        Debug.Assert(0 <= c && c < 4);
        if (x + DELTA < r.Length && y + DELTA < r[x + DELTA].Length) return r[x + DELTA][y + DELTA][c];
        if (x > 8 && y > 8)
        {
            int d = y - 6;
            var x2 = x - d;
            var y2 = y - d;
            var t1 = Calc(x2, y2, c);
            var t2 = Calc(x2 + 1, y2 + 1, c);
            if (Max(t1, t2) == ulong.MaxValue) return ulong.MaxValue;
            return t1 + (t2 - t1) * (uint)d;
        }
        if (x > 12)
        {
            int d = x - 10;
            var x2 = 10;
            var y2 = y;
            var t1 = Calc(x2, y2, c);
            var t2 = Calc(x2 + 1, y2, c);
            if (Max(t1, t2) == ulong.MaxValue) return ulong.MaxValue;
            return t1 + (t2 - t1) * (uint)d;
        }
        return ulong.MaxValue;
    }
    const int DELTA = 200;
    ulong[][][] r = NewArray(2 * DELTA + 1, 2 * DELTA + 1, 4, ulong.MaxValue);
    ulong[][] lens = NewArray(4, 4, ulong.MaxValue);
    int X, Y;
    int Ix(int ix)
    {
        // ↑
        // ↑ 横長の北東向き
        // →→→→→→→→→→→
        if (ix >= 4) return ix;
        if (Abs(X) < Abs(Y))
        {
            if (X >= 0 && Y >= 0)
                return ix switch
                {
                    0 => 1,
                    1 => 0,
                    2 => 3,
                    _ => 2,
                };
            else if (X >= 0)
                return ix switch
                {
                    0 => 1,
                    3 => 0,
                    2 => 3,
                    _ => 2,
                };
            else if (Y >= 0)
                return ix switch
                {
                    0 => 3,
                    3 => 0,
                    2 => 1,
                    _ => 2,
                };
            else
                return ix switch
                {
                    0 => 3,
                    1 => 2,
                    2 => 1,
                    _ => 0,
                };
        }
        else
        {
            if (X >= 0 && Y >= 0)
                return ix;
            else if (X >= 0)
                return ix switch
                {
                    1 => 3,
                    3 => 1,
                    _ => ix,
                };
            else if (Y >= 0)
                return ix switch
                {
                    0 => 2,
                    2 => 0,
                    _ => ix,
                };
            else
                return ix switch
                {
                    0 => 2,
                    1 => 3,
                    2 => 0,
                    3 => 1,
                    _ => ix,
                };
        }
    }
    WGraph<ulong, ULongOperator, WGraphNode<ulong>, WEdge<ulong>> graph;
}
#region Expanded by https://github.com/naminodarie/SourceExpander
//LICENSE: https://github.com/naminodarie/Kzrnm.Competitive/blob/master/LICENSE
namespace AtCoder{using static MethodImplOptions;public readonly struct ULongOperator:INumOperator<ulong>,IShiftOperator<ulong>{public ulong MinValue=>ulong.MinValue;public ulong MaxValue=>ulong.MaxValue;public ulong MultiplyIdentity=>1UL;[MethodImpl(AggressiveInlining)]public ulong Add(ulong x,ulong y)=>x+y;[MethodImpl(AggressiveInlining)]public ulong Subtract(ulong x,ulong y)=>x-y;[MethodImpl(AggressiveInlining)]public ulong Multiply(ulong x,ulong y)=>x*y;[MethodImpl(AggressiveInlining)]public ulong Divide(ulong x,ulong y)=>x/y;[MethodImpl(AggressiveInlining)]public ulong Modulo(ulong x,ulong y)=>x%y;[MethodImpl(AggressiveInlining)]public ulong Minus(ulong x)=>throw new InvalidOperationException("Ulong type cannot be negative.");[MethodImpl(AggressiveInlining)]public ulong Increment(ulong x)=> ++x;[MethodImpl(AggressiveInlining)]public ulong Decrement(ulong x)=> --x;[MethodImpl(AggressiveInlining)]public bool GreaterThan(ulong x,ulong y)=>x>y;[MethodImpl(AggressiveInlining)]public bool GreaterThanOrEqual(ulong x,ulong y)=>x>=y;[MethodImpl(AggressiveInlining)]public bool LessThan(ulong x,ulong y)=>x<y;[MethodImpl(AggressiveInlining)]public bool LessThanOrEqual(ulong x,ulong y)=>x<=y;[MethodImpl(AggressiveInlining)]public int Compare(ulong x,ulong y)=>x.CompareTo(y);[MethodImpl(AggressiveInlining)]public ulong LeftShift(ulong x,int y)=>x<<y;[MethodImpl(AggressiveInlining)]public ulong RightShift(ulong x,int y)=>x>>y;}}
namespace AtCoder.Internal{public class PriorityQueueOp<TKey,TValue,TKOp>:IPriorityQueueOp<KeyValuePair<TKey,TValue>>,IEnumerable where TKOp:IComparer<TKey>{protected TKey[]keys;protected TValue[]values;protected readonly TKOp _comparer;internal const int DefaultCapacity=16;public PriorityQueueOp():this(default(TKOp)){}public PriorityQueueOp(int capacity):this(capacity,default(TKOp)){}public PriorityQueueOp(TKOp comparer):this(DefaultCapacity,comparer){}public PriorityQueueOp(int capacity,TKOp comparer){if(comparer==null)throw new ArgumentNullException(nameof(comparer));int size=Math.Max(capacity,DefaultCapacity);keys=new TKey[size];values=new TValue[size];_comparer=comparer;}public int Count{get;private set;}=0;public KeyValuePair<TKey,TValue>Peek=>KeyValuePair.Create(keys[0],values[0]);[MethodImpl(MethodImplOptions.AggressiveInlining)]internal void Resize(){Array.Resize(ref keys,keys.Length<<1);Array.Resize(ref values,values.Length<<1);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Add(KeyValuePair<TKey,TValue>pair)=>Add(pair.Key,pair.Value);[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Add(TKey key,TValue value){if(Count>=keys.Length)Resize();keys[Count]=key;values[Count++]=value;UpdateUp(Count-1);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public bool TryDequeue(out TKey key,out TValue value){if(Count==0){key=default(TKey);value=default(TValue);return false;}(key,value)=Dequeue();return true;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public bool TryDequeue(out KeyValuePair<TKey,TValue>result){if(Count==0){result=default(KeyValuePair<TKey,TValue>);return false;}result=Dequeue();return true;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public KeyValuePair<TKey,TValue>Dequeue(){var res=KeyValuePair.Create(keys[0],values[0]);keys[0]=keys[ --Count];values[0]=values[Count];UpdateDown(0);return res;}[MethodImpl(MethodImplOptions.AggressiveInlining)]protected internal void UpdateUp(int i){var tar=keys[i];var tarVal=values[i];while(i>0){var p=(i-1)>>1;if(_comparer.Compare(tar,keys[p])>=0)break;keys[i]=keys[p];values[i]=values[p];i=p;}keys[i]=tar;values[i]=tarVal;}[MethodImpl(MethodImplOptions.AggressiveInlining)]protected internal void UpdateDown(int i){var tar=keys[i];var tarVal=values[i];var n=Count;var child=2*i+1;while(child<n){if(child!=n-1&&_comparer.Compare(keys[child],keys[child+1])>0)child++;if(_comparer.Compare(tar,keys[child])<=0)break;keys[i]=keys[child];values[i]=values[child];i=child;child=2*i+1;}keys[i]=tar;values[i]=tarVal;}public void Clear()=>Count=0;private KeyValuePair<TKey,TValue>[]GetItems(){var keys=new ArraySegment<TKey>(this.keys,0,Count).ToArray();var values=new ArraySegment<TValue>(this.values,0,Count).ToArray();Array.Sort(keys,values,_comparer);var arr=new KeyValuePair<TKey,TValue>[Count];for(int i=0;i<arr.Length;i++)arr[i]=KeyValuePair.Create(keys[i],values[i]);return arr;}IEnumerator IEnumerable.GetEnumerator()=>GetItems().GetEnumerator();private class DebugView{private readonly PriorityQueueOp<TKey,TValue,TKOp>pq;public DebugView(PriorityQueueOp<TKey,TValue,TKOp>pq){this.pq=pq;}public KeyValuePair<TKey,TValue>[]Items=>pq.GetItems();}}}
namespace Kzrnm.Competitive.IO{public partial class ConsoleWriter:IDisposable{private const int DefaultBufferSize=1<<12;public StreamWriter StreamWriter{get;}public ConsoleWriter():this(Console.OpenStandardOutput(),Console.OutputEncoding,DefaultBufferSize){}public ConsoleWriter(Stream output,Encoding encoding):this(output,encoding,DefaultBufferSize){}public ConsoleWriter(Stream output,Encoding encoding,int bufferSize){StreamWriter=new StreamWriter(output,encoding,bufferSize);}public void Flush()=>StreamWriter.Flush();public ConsoleWriter WriteLine(){StreamWriter.WriteLine();return this;}public ConsoleWriter WriteLine<T>(T obj){StreamWriter.WriteLine(obj.ToString());return this;}public ConsoleWriter WriteLineJoin<T>(IEnumerable<T>col)=>WriteMany(' ',col);public ConsoleWriter WriteLineJoin<T1,T2>((T1,T2)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2);public ConsoleWriter WriteLineJoin<T1,T2,T3>((T1,T2,T3)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3);public ConsoleWriter WriteLineJoin<T1,T2,T3,T4>((T1,T2,T3,T4)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3,tuple.Item4);public ConsoleWriter WriteLineJoin<TTuple>(TTuple tuple)where TTuple:ITuple{var col=new object[tuple.Length];for(int i=0;i<col.Length;i++)col[i]=tuple[i];return WriteLineJoin(col);}public ConsoleWriter WriteLineJoin(params object[]col)=>WriteMany(' ',col);public ConsoleWriter WriteLineJoin<T1,T2>(T1 v1,T2 v2){StreamWriter.Write(v1.ToString());StreamWriter.Write(' ');StreamWriter.WriteLine(v2.ToString());return this;}public ConsoleWriter WriteLineJoin<T1,T2,T3>(T1 v1,T2 v2,T3 v3){StreamWriter.Write(v1.ToString());StreamWriter.Write(' ');StreamWriter.Write(v2.ToString());StreamWriter.Write(' ');StreamWriter.WriteLine(v3.ToString());return this;}public ConsoleWriter WriteLineJoin<T1,T2,T3,T4>(T1 v1,T2 v2,T3 v3,T4 v4){StreamWriter.Write(v1.ToString());StreamWriter.Write(' ');StreamWriter.Write(v2.ToString());StreamWriter.Write(' ');StreamWriter.Write(v3.ToString());StreamWriter.Write(' ');StreamWriter.WriteLine(v4.ToString());return this;}public ConsoleWriter WriteLines<T>(IEnumerable<T>col)=>WriteMany('\n',col);public ConsoleWriter WriteLineGrid<T>(IEnumerable<IEnumerable<T>>cols){foreach(var col in cols)WriteLineJoin(col);return this;}protected ConsoleWriter WriteMany<T>(char sep,IEnumerable<T>col){var en=col.GetEnumerator();if(!en.MoveNext())goto End;StreamWriter.Write(en.Current.ToString());while(en.MoveNext()){StreamWriter.Write(sep);StreamWriter.Write(en.Current.ToString());}End:StreamWriter.WriteLine();return this;}public void Dispose()=>Flush();}}
namespace Kzrnm.Competitive.IO{public partial class ConsoleWriter{public ConsoleWriter WriteLine(ReadOnlySpan<char>obj){StreamWriter.WriteLine(obj);return this;}public ConsoleWriter WriteLineJoin<T>(Span<T>col)=>WriteMany(' ',(ReadOnlySpan<T>)col);public ConsoleWriter WriteLineJoin<T>(ReadOnlySpan<T>col)=>WriteMany(' ',col);public ConsoleWriter WriteLines<T>(Span<T>col)=>WriteMany('\n',(ReadOnlySpan<T>)col);public ConsoleWriter WriteLines<T>(ReadOnlySpan<T>col)=>WriteMany('\n',col);protected ConsoleWriter WriteMany<T>(char sep,ReadOnlySpan<T>col){var en=col.GetEnumerator();if(!en.MoveNext())return this;StreamWriter.Write(en.Current.ToString());while(en.MoveNext()){StreamWriter.Write(sep);StreamWriter.Write(en.Current.ToString());}StreamWriter.WriteLine();return this;}}}
namespace Kzrnm.Competitive.IO{using static MethodImplOptions;public class PropertyConsoleReader{private const int BufSize=1<<12;private readonly Stream input;private readonly Encoding encoding;internal readonly byte[]buffer=new byte[BufSize];internal int pos=0;internal int len=0;public PropertyConsoleReader():this(Console.OpenStandardInput(),Console.InputEncoding){}public PropertyConsoleReader(Stream input,Encoding encoding){this.input=input;this.encoding=encoding;}[MethodImpl(AggressiveInlining)]protected internal byte Read(){if( ++pos>=len){if((len=input.Read(buffer,0,buffer.Length))<=0){buffer[0]=10;}pos=0;}return buffer[pos];}public int Int{[MethodImpl(AggressiveInlining)]get{int res=0;bool neg=false;byte b;do{b=Read();if(b=='-')neg=true;}while(b<'0');do{res=res*10+(b^'0');b=Read();}while('0'<=b);return neg?-res:res;}}public int Int0{[MethodImpl(AggressiveInlining)]get=>Int-1;}public long Long{[MethodImpl(AggressiveInlining)]get{long res=0;bool neg=false;byte b;do{b=Read();if(b=='-')neg=true;}while(b<'0');do{res=res*10+(b^'0');b=Read();}while('0'<=b);return neg?-res:res;}}public long Long0{[MethodImpl(AggressiveInlining)]get=>Long-1;}public ulong ULong{[MethodImpl(AggressiveInlining)]get{ulong res=0;byte b;do b=Read();while(b<'0');do{res=res*10+(b^(ulong)'0');b=Read();}while('0'<=b);return res;}}public ulong ULong0{[MethodImpl(AggressiveInlining)]get=>ULong-1;}public string String{[MethodImpl(AggressiveInlining)]get{var sb=new List<byte>();;byte b;do b=Read();while(b<=' ');do{sb.Add(b);b=Read();}while(' '<b);return encoding.GetString(sb.ToArray());}}public string Ascii{[MethodImpl(AggressiveInlining)]get{var sb=new StringBuilder();byte b;do b=Read();while(b<=' ');do{sb.Append((char)b);b=Read();}while(' '<b);return sb.ToString();}}public string Line{[MethodImpl(AggressiveInlining)]get{var sb=new List<byte>();byte b;do b=Read();while(b<=' ');do{sb.Add(b);b=Read();}while(b!='\n'&&b!='\r');return encoding.GetString(sb.ToArray());}}public char Char{[MethodImpl(AggressiveInlining)]get{byte b;do b=Read();while(b<=' ');return(char)b;}}public double Double{[MethodImpl(AggressiveInlining)]get{return double.Parse(Ascii);}}public decimal Decimal{[MethodImpl(AggressiveInlining)]get{return decimal.Parse(Ascii);}}[MethodImpl(AggressiveInlining)]public static implicit operator int(PropertyConsoleReader cr)=>cr.Int;[MethodImpl(AggressiveInlining)]public static implicit operator long(PropertyConsoleReader cr)=>cr.Long;[MethodImpl(AggressiveInlining)]public static implicit operator ulong(PropertyConsoleReader cr)=>cr.ULong;[MethodImpl(AggressiveInlining)]public static implicit operator double(PropertyConsoleReader cr)=>cr.Double;[MethodImpl(AggressiveInlining)]public static implicit operator decimal(PropertyConsoleReader cr)=>cr.Decimal;[MethodImpl(AggressiveInlining)]public static implicit operator string(PropertyConsoleReader cr)=>cr.Ascii;}}
namespace Kzrnm.Competitive{public static class PriorityQueue{public static PriorityQueueOp<T,DefaultComparerStruct<T>>Create<T>()where T:IComparable<T> =>new PriorityQueueOp<T,DefaultComparerStruct<T>>();public static PriorityQueueOp<T,DefaultComparerStruct<T>>Create<T>(int capacity)where T:IComparable<T> =>new PriorityQueueOp<T,DefaultComparerStruct<T>>(capacity);public static PriorityQueueOp<T,TOp>Create<T,TOp>()where TOp:struct,IComparer<T> =>new PriorityQueueOp<T,TOp>(default(TOp));public static PriorityQueueOp<T,TOp>Create<T,TOp>(TOp comparer)where TOp:IComparer<T> =>new PriorityQueueOp<T,TOp>(comparer);public static PriorityQueueOp<T,TOp>Create<T,TOp>(int capacity)where TOp:IComparer<T> =>new PriorityQueueOp<T,TOp>(capacity,default(TOp));public static PriorityQueueOp<T,TOp>Create<T,TOp>(int capacity,TOp comparer)where TOp:IComparer<T> =>new PriorityQueueOp<T,TOp>(capacity,comparer);public static PriorityQueueOp<TKey,TValue,DefaultComparerStruct<TKey>>CreateDictionary<TKey,TValue>()where TKey:IComparable<TKey> =>new PriorityQueueOp<TKey,TValue,DefaultComparerStruct<TKey>>();public static PriorityQueueOp<TKey,TValue,DefaultComparerStruct<TKey>>CreateDictionary<TKey,TValue>(int capacity)where TKey:IComparable<TKey> =>new PriorityQueueOp<TKey,TValue,DefaultComparerStruct<TKey>>(capacity);public static PriorityQueueOp<TKey,TValue,TOp>CreateDictionary<TKey,TValue,TOp>()where TOp:struct,IComparer<TKey> =>new PriorityQueueOp<TKey,TValue,TOp>(default(TOp));public static PriorityQueueOp<TKey,TValue,TOp>CreateDictionary<TKey,TValue,TOp>(TOp comparer)where TOp:IComparer<TKey> =>new PriorityQueueOp<TKey,TValue,TOp>(comparer);public static PriorityQueueOp<TKey,TValue,TOp>CreateDictionary<TKey,TValue,TOp>(int capacity)where TOp:IComparer<TKey> =>new PriorityQueueOp<TKey,TValue,TOp>(capacity,default(TOp));public static PriorityQueueOp<TKey,TValue,TOp>CreateDictionary<TKey,TValue,TOp>(int capacity,TOp comparer)where TOp:IComparer<TKey> =>new PriorityQueueOp<TKey,TValue,TOp>(capacity,comparer);}}
namespace Kzrnm.Competitive{using static MethodImplOptions;public static class UpdateExtension{[MethodImpl(AggressiveInlining)]public static bool UpdateMax<T>(this ref T r,T val)where T:struct,IComparable<T>{if(r.CompareTo(val)<0){r=val;return true;}return false;}[MethodImpl(AggressiveInlining)]public static bool UpdateMin<T>(this ref T r,T val)where T:struct,IComparable<T>{if(r.CompareTo(val)>0){r=val;return true;}return false;}}}
namespace Kzrnm.Competitive{public static class Global{public static T[]NewArray<T>(int len0,T value)where T:struct=>new T[len0].Fill(value);public static T[]NewArray<T>(int len0,Func<T>factory){var arr=new T[len0];for(int i=0;i<arr.Length;i++)arr[i]=factory();return arr;}public static T[][]NewArray<T>(int len0,int len1,T value)where T:struct{var arr=new T[len0][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,value);return arr;}public static T[][]NewArray<T>(int len0,int len1,Func<T>factory){var arr=new T[len0][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,factory);return arr;}public static T[][][]NewArray<T>(int len0,int len1,int len2,T value)where T:struct{var arr=new T[len0][][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,len2,value);return arr;}public static T[][][]NewArray<T>(int len0,int len1,int len2,Func<T>factory){var arr=new T[len0][][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,len2,factory);return arr;}public static T[][][][]NewArray<T>(int len0,int len1,int len2,int len3,T value)where T:struct{var arr=new T[len0][][][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,len2,len3,value);return arr;}public static T[][][][]NewArray<T>(int len0,int len1,int len2,int len3,Func<T>factory){var arr=new T[len0][][][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,len2,len3,factory);return arr;}}}
namespace Kzrnm.Competitive{public static class 最短経路Dijkstra{public static T[]Dijkstra<T,TOp,TNode,TEdge>(this IWGraph<T,TOp,TNode,TEdge>graph,int from)where T:struct where TOp:struct,INumOperator<T>where TNode:IGraphNode<TEdge>where TEdge:IWEdge<T>{TOp op=default;var graphArr=graph.AsArray();var INF=op.MaxValue;var res=Global.NewArray(graphArr.Length,INF);res[from]=default;var used=new bool[graphArr.Length];int count=0;var remains=new PriorityQueueOp<T,int,TOp>{{default,from}};while(remains.TryDequeue(out var len,out var ix)){if(used[ix])continue;used[ix]=true;if( ++count>=graphArr.Length)break;foreach(var e in graphArr[ix].Children){var nextLength=op.Add(len,e.Value);if(op.GreaterThan(res[e.To],nextLength))remains.Add(res[e.To]=nextLength,e.To);}}return res;}}}
namespace Kzrnm.Competitive{public interface IWGraph<T,TOp,TNode,TEdge>:IGraph<TNode,TEdge>where TOp:struct,IAdditionOperator<T>where TNode:IGraphNode<TEdge>where TEdge:IWEdge<T>{}public interface IWTreeGraph<T,TOp,TNode,TEdge>:ITreeGraph<TNode,TEdge>where TOp:struct,IAdditionOperator<T>where TNode:ITreeNode<TEdge>where TEdge:IWEdge<T>{}public class WGraph<T,TOp,TNode,TEdge>:IWGraph<T,TOp,TNode,TEdge>where TOp:struct,IAdditionOperator<T>where TNode:IGraphNode<TEdge>where TEdge:IWEdge<T>{public CSR<TEdge>Edges{get;}internal TNode[]Nodes{get;}public TNode[]AsArray()=>Nodes;public TNode this[int index]=>Nodes[index];public int Length=>Nodes.Length;public WGraph(TNode[]array,CSR<TEdge>edges){this.Nodes=array;this.Edges=edges;}}public class WTreeGraph<T,TOp,TNode,TEdge>:IWTreeGraph<T,TOp,TNode,TEdge>where TOp:struct,IAdditionOperator<T>where TNode:ITreeNode<TEdge>where TEdge:IWEdge<T>{internal TNode[]Nodes{get;}public TNode[]AsArray()=>Nodes;public TNode this[int index]=>Nodes[index];public int Length=>Nodes.Length;public int Root{get;}public WTreeGraph(TNode[]array,int root){this.Root=root;this.Nodes=array;}}}
namespace Kzrnm.Competitive{public class WGraphBuilder<T,TOp>where TOp:struct,IAdditionOperator<T>{protected static readonly TOp op=default;internal readonly EdgeContainer<WEdge<T>>edgeContainer;public WGraphBuilder(int size,bool isDirected){edgeContainer=new EdgeContainer<WEdge<T>>(size,isDirected);}public void Add(int from,int to,T value)=>edgeContainer.Add(from,new WEdge<T>(to,value));public WGraph<T,TOp,WGraphNode<T>,WEdge<T>>ToGraph(){var res=new WGraphNode<T>[edgeContainer.Length];var csr=edgeContainer.ToCSR();var counter=new int[res.Length];var rootCounter=edgeContainer.IsDirected?new int[res.Length]:counter;var children=new WEdge<T>[res.Length][];var roots=edgeContainer.IsDirected?new WEdge<T>[res.Length][]:children;for(int i=0;i<res.Length;i++){if(children[i]==null)children[i]=new WEdge<T>[edgeContainer.sizes[i]];if(roots[i]==null)roots[i]=new WEdge<T>[edgeContainer.rootSizes[i]];res[i]=new WGraphNode<T>(i,roots[i],children[i]);foreach(ref var e in csr.EList.AsSpan(csr.Start[i],csr.Start[i+1]-csr.Start[i])){if(roots[e.To]==null)roots[e.To]=new WEdge<T>[edgeContainer.rootSizes[e.To]];children[i][counter[i]++]=e;roots[e.To][rootCounter[e.To]++]=e.Reversed(i);}}return new WGraph<T,TOp,WGraphNode<T>,WEdge<T>>(res,csr);}public WTreeGraph<T,TOp,WTreeNode<T>,WEdge<T>>ToTree(int root=0){var res=new WTreeNode<T>[edgeContainer.Length];var children=new SimpleList<WEdge<T>>[res.Length];foreach(var(from,e)in edgeContainer.edges){if(children[from]==null)children[from]=new SimpleList<WEdge<T>>();if(children[e.To]==null)children[e.To]=new SimpleList<WEdge<T>>();children[from].Add(e);children[e.To].Add(e.Reversed(from));}if(edgeContainer.Length==1){return new WTreeGraph<T,TOp,WTreeNode<T>,WEdge<T>>(new WTreeNode<T>[1]{new WTreeNode<T>(root,WEdge<T>.None,0,default,Array.Empty<WEdge<T>>())},root);}res[root]=new WTreeNode<T>(root,WEdge<T>.None,0,default,children[root].ToArray());var queue=new Queue<(int parent,int child,T value)>();foreach(var e in res[root].Children){queue.Enqueue((root,e.To,e.Value));}while(queue.Count>0){var(parent,cur,value)=queue.Dequeue();IList<WEdge<T>>childrenBuilder;if(parent==-1)childrenBuilder=children[cur];else{childrenBuilder=new SimpleList<WEdge<T>>(children[cur].Count);foreach(var e in children[cur])if(e.To!=parent)childrenBuilder.Add(e);}var childrenArr=childrenBuilder.ToArray();res[cur]=new WTreeNode<T>(cur,new WEdge<T>(parent,value),res[parent].Depth+1,op.Add(res[parent].DepthLength,value),childrenArr);foreach(var e in childrenArr){queue.Enqueue((cur,e.To,e.Value));}}return new WTreeGraph<T,TOp,WTreeNode<T>,WEdge<T>>(res,root);}}public readonly struct WEdge<T>:IWEdge<T>,IReversable<WEdge<T>>,IEquatable<WEdge<T>>{public static WEdge<T>None{get;}=new WEdge<T>(-1,default);public WEdge(int to,T value){To=to;Value=value;}public int To{get;}public T Value{get;}public override bool Equals(object obj)=>obj is WEdge<T>edge&&this.Equals(edge);public bool Equals(WEdge<T>other)=>this.To==other.To&&EqualityComparer<T>.Default.Equals(this.Value,other.Value);public override int GetHashCode()=>HashCode.Combine(this.To,this.Value);public static bool operator==(WEdge<T>left,WEdge<T>right)=>left.Equals(right);public static bool operator!=(WEdge<T>left,WEdge<T>right)=>!(left==right);public override string ToString()=>(To,Value).ToString();public WEdge<T>Reversed(int from)=>new WEdge<T>(from,Value);}public class WGraphNode<T>:IGraphNode<WEdge<T>>,IEquatable<WGraphNode<T>>{public WGraphNode(int i,WEdge<T>[]roots,WEdge<T>[]children){this.Index=i;this.Roots=roots;this.Children=children;}public int Index{get;}public WEdge<T>[]Roots{get;}public WEdge<T>[]Children{get;}public bool IsDirected=>Roots!=Children;public override string ToString()=>$"children: {string.Join(",",Children)}";public override bool Equals(object obj)=>obj is WGraphNode<T>d&&this.Equals(d);public bool Equals(WGraphNode<T>other)=>this.Index==other.Index;public override int GetHashCode()=>this.Index;}public class WTreeNode<T>:ITreeNode<WEdge<T>>,IEquatable<WTreeNode<T>>{public WTreeNode(int i,WEdge<T>root,int depth,T depthLength,WEdge<T>[]children){this.Index=i;this.Root=root;this.Children=children;this.Depth=depth;this.DepthLength=depthLength;}public int Index{get;}public WEdge<T>Root{get;}public WEdge<T>[]Children{get;}public int Depth{get;}public T DepthLength{get;}public override string ToString()=>$"children: {string.Join(",",Children)}";public override bool Equals(object obj)=>obj is WTreeNode<T>node&&this.Equals(node);public bool Equals(WTreeNode<T>other)=>other!=null&&this.Index==other.Index;public override int GetHashCode()=>this.Index;}}
namespace Kzrnm.Competitive{public class WULongGraphBuilder:WGraphBuilder<ulong,ULongOperator>{public WULongGraphBuilder(int count,bool isDirected):base(count,isDirected){}public static WULongGraphBuilder Create(int count,PropertyConsoleReader cr,int edgeCount,bool isDirected){var gb=new WULongGraphBuilder(count,isDirected);for(var i=0;i<edgeCount;i++)gb.Add(cr.Int0,cr.Int0,cr.ULong);return gb;}public static WULongGraphBuilder CreateTree(int count,PropertyConsoleReader cr){var gb=new WULongGraphBuilder(count,false);for(var i=1;i<count;i++)gb.Add(cr.Int0,cr.Int0,cr.ULong);return gb;}}}
internal partial class Program{static void Main()=>new Program(new PropertyConsoleReader(),new ConsoleWriter()).Run();public PropertyConsoleReader cr;public ConsoleWriter cw;public Program(PropertyConsoleReader r,ConsoleWriter w){this.cr=r;this.cw=w;CultureInfo.CurrentCulture=CultureInfo.InvariantCulture;}public void Run(){int Q=1;if(__ManyTestCases())Q=cr;for(;Q>0;Q--){var res=Calc();if(res is double d)cw.WriteLine(d.ToString("0.####################",CultureInfo.InvariantCulture));else if(res is bool b)WriteBool(b);else if(res!=null)cw.WriteLine(res.ToString());}cw.Flush();}partial void WriteBool(bool b);object Calc(Program dum=null)=>dum;bool __ManyTestCases(Program dum=null)=>false;}
namespace AtCoder{public interface IAdditionOperator<T>{T Add(T x,T y);T Subtract(T x,T y);}public interface IMultiplicationOperator<T>{T Multiply(T x,T y);T MultiplyIdentity{get;}}public interface IDivisionOperator<T>:IMultiplicationOperator<T>{T Divide(T x,T y);T Modulo(T x,T y);}public interface IUnaryNumOperator<T>{T Minus(T x);T Increment(T x);T Decrement(T x);}public interface IArithmeticOperator<T>:IAdditionOperator<T>,IMultiplicationOperator<T>,IDivisionOperator<T>,IUnaryNumOperator<T>{}public interface ICompareOperator<T>:IComparer<T>{bool GreaterThan(T x,T y);bool GreaterThanOrEqual(T x,T y);bool LessThan(T x,T y);bool LessThanOrEqual(T x,T y);}public interface INumOperator<T>:IArithmeticOperator<T>,ICompareOperator<T>{T MinValue{get;}T MaxValue{get;}}public interface IShiftOperator<T>{T LeftShift(T x,int y);T RightShift(T x,int y);}}
namespace AtCoder.Internal{public interface IPriorityQueueOp<T>{int Count{get;}T Peek{get;}void Add(T value);T Dequeue();bool TryDequeue(out T result);void Clear();}}
namespace AtCoder.Internal{public class PriorityQueueOp<T,TOp>:IPriorityQueueOp<T>,IEnumerable where TOp:IComparer<T>{protected T[]data;protected readonly TOp _comparer;internal const int DefaultCapacity=16;public PriorityQueueOp():this(default(TOp)){}public PriorityQueueOp(int capacity):this(capacity,default(TOp)){}public PriorityQueueOp(TOp comparer):this(DefaultCapacity,comparer){}public PriorityQueueOp(int capacity,TOp comparer){if(comparer==null)throw new ArgumentNullException(nameof(comparer));data=new T[Math.Max(capacity,DefaultCapacity)];_comparer=comparer;}public int Count{get;private set;}=0;public T Peek=>data[0];[MethodImpl(MethodImplOptions.AggressiveInlining)]internal void Resize(){Array.Resize(ref data,data.Length<<1);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Add(T value){if(Count>=data.Length)Resize();data[Count++]=value;UpdateUp(Count-1);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public bool TryDequeue(out T result){if(Count==0){result=default(T);return false;}result=Dequeue();return true;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public T Dequeue(){var res=data[0];data[0]=data[ --Count];UpdateDown(0);return res;}[MethodImpl(MethodImplOptions.AggressiveInlining)]protected internal void UpdateUp(int i){var tar=data[i];while(i>0){var p=(i-1)>>1;if(_comparer.Compare(tar,data[p])>=0)break;data[i]=data[p];i=p;}data[i]=tar;}[MethodImpl(MethodImplOptions.AggressiveInlining)]protected internal void UpdateDown(int i){var tar=data[i];var n=Count;var child=2*i+1;while(child<n){if(child!=n-1&&_comparer.Compare(data[child],data[child+1])>0)child++;if(_comparer.Compare(tar,data[child])<=0)break;data[i]=data[child];i=child;child=2*i+1;}data[i]=tar;}public void Clear()=>Count=0;private T[]GetItems(){var arr=new ArraySegment<T>(data,0,Count).ToArray();Array.Sort(arr,_comparer);return arr;}IEnumerator IEnumerable.GetEnumerator()=>GetItems().GetEnumerator();private class DebugView{private readonly PriorityQueueOp<T,TOp>pq;public DebugView(PriorityQueueOp<T,TOp>pq){this.pq=pq;}public T[]Items=>pq.GetItems();}}}
namespace Kzrnm.Competitive{public struct DefaultComparerStruct<T>:IComparer<T>where T:IComparable<T>{public static DefaultComparerStruct<T>Default{get;}=default;public int Compare(T x,T y)=>x.CompareTo(y);public override bool Equals(object obj)=>obj is ReverseComparerStruct<T>;public override int GetHashCode()=>GetType().GetHashCode();}}
namespace Kzrnm.Competitive{using static MethodImplOptions;public static class ArrayExtension{[MethodImpl(AggressiveInlining)]public static T[]Fill<T>(this T[]arr,T value){arr.AsSpan().Fill(value);return arr;}[MethodImpl(AggressiveInlining)]public static T[]Sort<T>(this T[]arr){Array.Sort(arr);return arr;}[MethodImpl(AggressiveInlining)]public static string[]Sort(this string[]arr)=>Sort(arr,StringComparer.Ordinal);[MethodImpl(AggressiveInlining)]public static T[]Sort<T,U>(this T[]arr,Expression<Func<T,U>>selector)where U:IComparable<U> =>Sort(arr,ExComparer<T>.CreateExp(selector));[MethodImpl(AggressiveInlining)]public static T[]Sort<T>(this T[]arr,Comparison<T>comparison){Array.Sort(arr,comparison);return arr;}[MethodImpl(AggressiveInlining)]public static T[]Sort<T>(this T[]arr,IComparer<T>comparer){Array.Sort(arr,comparer);return arr;}[MethodImpl(AggressiveInlining)]public static T[]Reverse<T>(this T[]arr){Array.Reverse(arr);return arr;}[MethodImpl(AggressiveInlining)]public static ref T Get<T>(this T[]arr,int index){if(index<0)return ref arr[arr.Length+index];return ref arr[index];}[MethodImpl(AggressiveInlining)]public static ref T GetOrDummy<T>(this T[]arr,int index,T dummy=default){if((uint)index<(uint)arr.Length)return ref arr[index];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[MethodImpl(AggressiveInlining)]public static ref T GetOrDummy<T>(this T[][]arr,int index1,int index2,T dummy=default){if((uint)index1<(uint)arr.Length&&(uint)index2<(uint)arr[index1].Length)return ref arr[index1][index2];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[MethodImpl(AggressiveInlining)]public static ref T GetOrDummy<T>(this T[][][]arr,int index1,int index2,int index3,T dummy=default){if((uint)index1<(uint)arr.Length&&(uint)index2<(uint)arr[index1].Length&&(uint)index3<(uint)arr[index1][index2].Length)return ref arr[index1][index2][index3];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}private static class Dummy<T>{public static T dummy;}}}
namespace Kzrnm.Competitive{public interface IReversable<T>where T:IEdge{T Reversed(int from);}public interface IEdge{int To{get;}}public interface IWEdge<T>:IEdge{T Value{get;}}public interface IGraphNode<out TEdge>where TEdge:IEdge{int Index{get;}TEdge[]Roots{get;}TEdge[]Children{get;}bool IsDirected{get;}}public interface ITreeNode<TEdge>where TEdge:IEdge{int Index{get;}TEdge Root{get;}TEdge[]Children{get;}int Depth{get;}}}
namespace Kzrnm.Competitive{public interface IGraph<TNode,TEdge>where TNode:IGraphNode<TEdge>where TEdge:IEdge{CSR<TEdge>Edges{get;}TNode[]AsArray();TNode this[int index]{get;}int Length{get;}}public interface ITreeGraph<TNode,TEdge>where TNode:ITreeNode<TEdge>where TEdge:IEdge{int Root{get;}TNode[]AsArray();TNode this[int index]{get;}int Length{get;}}public class SimpleGraph<TNode,TEdge>:IGraph<TNode,TEdge>where TNode:IGraphNode<TEdge>where TEdge:IEdge{public CSR<TEdge>Edges{get;}internal TNode[]Nodes{get;}public TNode[]AsArray()=>Nodes;public TNode this[int index]=>Nodes[index];public int Length=>Nodes.Length;public SimpleGraph(TNode[]array,CSR<TEdge>edges){this.Nodes=array;this.Edges=edges;}}public class TreeGraph<TNode,TEdge>:ITreeGraph<TNode,TEdge>where TNode:ITreeNode<TEdge>where TEdge:IEdge{internal TNode[]Nodes{get;}public TNode[]AsArray()=>Nodes;public TNode this[int index]=>Nodes[index];public int Length=>Nodes.Length;public int Root{get;}public TreeGraph(TNode[]array,int root){this.Root=root;this.Nodes=array;}}}
namespace AtCoder.Internal{public class CSR<TEdge>{public readonly int[]Start;public readonly TEdge[]EList;public CSR(int n,ICollection<(int from,TEdge e)>edges){Start=new int[n+1];EList=new TEdge[edges.Count];foreach(var(from,_)in edges){Start[from+1]++;}for(int i=1;i<=n;i++){Start[i]+=Start[i-1];}var counter=(int[])Start.Clone();foreach(var(from,e)in edges){EList[counter[from]++]=e;}}}}
namespace Kzrnm.Competitive{public class EdgeContainer<TEdge>where TEdge:IEdge{public int Length{get;}public bool IsDirected{get;}public readonly SimpleList<(int from,TEdge edge)>edges;public readonly int[]sizes;public readonly int[]rootSizes;public EdgeContainer(int size,bool isDirected){Length=size;IsDirected=isDirected;sizes=new int[size];rootSizes=isDirected?new int[size]:sizes;edges=new SimpleList<(int from,TEdge edge)>(size);}public void Add(int from,TEdge edge){ ++sizes[from];++rootSizes[edge.To];edges.Add((from,edge));}public CSR<TEdge>ToCSR()=>new CSR<TEdge>(Length,edges);}}
namespace AtCoder.Internal{public class SimpleList<T>:IList<T>,IReadOnlyList<T>{private T[]data;private const int DefaultCapacity=2;public SimpleList(){data=new T[DefaultCapacity];}public SimpleList(int capacity){data=new T[Math.Max(capacity,DefaultCapacity)];}public SimpleList(IEnumerable<T>collection){if(collection is ICollection<T>col){data=new T[col.Count];col.CopyTo(data,0);Count=col.Count;}else{data=new T[DefaultCapacity];foreach(var item in collection)Add(item);}}public Span<T>AsSpan()=>new Span<T>(data,0,Count);public ref T this[int index]{[MethodImpl(MethodImplOptions.AggressiveInlining)]get{if((uint)index>=(uint)Count)ThrowIndexOutOfRangeException();return ref data[index];}}public int Count{get;private set;}public void Add(T item){if((uint)Count>=(uint)data.Length)Array.Resize(ref data,data.Length<<1);data[Count++]=item;}public void RemoveLast(){if( --Count<0)ThrowIndexOutOfRangeException();}public SimpleList<T>Reverse(){Array.Reverse(data,0,Count);return this;}public SimpleList<T>Reverse(int index,int count){Array.Reverse(data,index,count);return this;}public SimpleList<T>Sort(){Array.Sort(data,0,Count);return this;}public SimpleList<T>Sort(IComparer<T>comparer){Array.Sort(data,0,Count,comparer);return this;}public SimpleList<T>Sort(int index,int count,IComparer<T>comparer){Array.Sort(data,index,count,comparer);return this;}public void Clear()=>Count=0;public bool Contains(T item)=>IndexOf(item)>=0;public int IndexOf(T item)=>Array.IndexOf(data,item,0,Count);public void CopyTo(T[]array,int arrayIndex)=>Array.Copy(data,0,array,arrayIndex,Count);public T[]ToArray()=>AsSpan().ToArray();bool ICollection<T>.IsReadOnly=>false;T IList<T>.this[int index]{get=>data[index];set=>data[index]=value;}T IReadOnlyList<T>.this[int index]{get=>data[index];}void IList<T>.Insert(int index,T item)=>throw new NotSupportedException();bool ICollection<T>.Remove(T item)=>throw new NotSupportedException();void IList<T>.RemoveAt(int index)=>throw new NotSupportedException();IEnumerator IEnumerable.GetEnumerator()=>((IEnumerable<T>)this).GetEnumerator();IEnumerator<T>IEnumerable<T>.GetEnumerator(){for(int i=0;i<Count;i++)yield return data[i];}public Span<T>.Enumerator GetEnumerator()=>AsSpan().GetEnumerator();private static void ThrowIndexOutOfRangeException()=>throw new IndexOutOfRangeException();}}
namespace Kzrnm.Competitive{public struct ReverseComparerStruct<T>:IComparer<T>where T:IComparable<T>{public static ReverseComparerStruct<T>Default{get;}=default;public int Compare(T x,T y)=>y.CompareTo(x);public override bool Equals(object obj)=>obj is ReverseComparerStruct<T>;public override int GetHashCode()=>GetType().GetHashCode();}}
namespace Kzrnm.Competitive{public static class ExComparer<T>{class ExpressionComparer<K>:IComparer<T>where K:IComparable<K>{private class ParameterReplaceVisitor:ExpressionVisitor{private readonly ParameterExpression from;private readonly ParameterExpression to;public ParameterReplaceVisitor(ParameterExpression from,ParameterExpression to){this.from=from;this.to=to;}protected override Expression VisitParameter(ParameterExpression node)=>node==from?to:base.VisitParameter(node);}readonly Comparison<T>func;public ExpressionComparer(Expression<Func<T,K>>expression){var paramA=expression.Parameters[0];var paramB=Expression.Parameter(typeof(T));var f2=(Expression<Func<T,K>>)new ParameterReplaceVisitor(expression.Parameters[0],paramB).Visit(expression);var compExp=Expression.Lambda<Comparison<T>>(Expression.Call(expression.Body,typeof(K).GetMethod(nameof(IComparable<K>.CompareTo),new[]{typeof(K)}),f2.Body),paramA,paramB);this.func=compExp.Compile();}public int Compare(T x,T y)=>func(x,y);public override bool Equals(object obj)=>obj is ExpressionComparer<K>c&&this.func==c.func;public override int GetHashCode()=>func.GetHashCode();}public static IComparer<T>CreateExp<K>(Expression<Func<T,K>>expression)where K:IComparable<K> =>new ExpressionComparer<K>(expression);}}
#endregion Expanded by https://github.com/naminodarie/SourceExpander

Submission Info

Submission Time
Task C - Mansion
User naminodarie
Language C# (.NET Core 3.1.201)
Score 89
Code Size 40223 Byte
Status WA
Exec Time 597 ms
Memory 74740 KB

Judge Result

Set Name Set 1 Set 2 Set 3 Set 4 Set 5 Set 6 Set 7 Set 8 Set 9 Set 10 Set 11 Set 12 Set 13 Set 14 Set 15 Set 16 Set 17 Set 18 Set 19 Set 20 Set 21 Set 22 Set 23 Set 24 Set 25 Set 26 Set 27 Set 28 Set 29 Set 30 Set 31 Set 32 Set 33 Set 34 Set 35 Set 36 Set 37
Score / Max Score 1 / 1 1 / 1 1 / 1 1 / 1 1 / 1 1 / 1 1 / 1 1 / 1 1 / 1 1 / 1 1 / 1 1 / 1 1 / 1 1 / 1 0 / 1 1 / 1 1 / 1 1 / 1 1 / 1 1 / 1 1 / 1 2 / 2 2 / 2 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 0 / 10
Status
AC × 6
AC × 2
AC × 4
AC × 5
AC × 2
AC × 3
AC × 6
AC × 5
AC × 5
AC × 5
AC × 4
AC × 3
AC × 8
AC × 1
WA × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 3
AC × 2
AC × 4
AC × 2
AC × 3
AC × 2
AC × 4
AC × 4
AC × 9
AC × 2
AC × 2
AC × 3
AC × 2
AC × 3
AC × 2
WA × 1
Set Name Test Cases
Set 1 sa01-01, sa01-02, sa01-03, sa01-04, sa01-05, sa01-06
Set 2 sa02-01, sa02-02
Set 3 sb01-01, sb01-02, sb01-03, sb01-04
Set 4 sb02-01, sb02-02, sb02-03, sb02-04, sb02-05
Set 5 sc01-01, sc01-02
Set 6 sc02-01, sc02-02, sc02-03
Set 7 sd01-01, sd01-02, sd01-03, sd01-04, sd01-05, sd01-06
Set 8 sd02-01, sd02-02, sd02-03, sd02-04, sd02-05
Set 9 se01-01, se01-02, se01-03, se01-04, se01-05
Set 10 se02-01, se02-02, se02-03, se02-04, se02-05
Set 11 sf01-01, sf01-02, sf01-03, sf01-04
Set 12 sf02-01, sf02-02, sf02-03
Set 13 sg01-01, sg01-02, sg01-03, sg01-04, sg01-05, sg01-06, sg01-07, sg01-08
Set 14 sh01-01
Set 15 sh02-01
Set 16 sh03-01
Set 17 sh04-01
Set 18 sh05-01
Set 19 sh06-01
Set 20 sh07-01
Set 21 sh08-01
Set 22 sh09-01
Set 23 sh10-01, sh10-02, sh10-03
Set 24 si01-01, si01-02
Set 25 la01-01, la01-02, la01-03, la01-04
Set 26 la02-01, la02-02
Set 27 lb01-01, lb01-02, lb01-03
Set 28 lb02-01, lb02-02
Set 29 lc01-01, lc01-02, lc01-03, lc01-04
Set 30 le01-01, le01-02, le01-03, le01-04
Set 31 lj01-01, lj01-02, lj01-03, lj01-04, lj01-05, lj01-06, lj01-07, lj01-08, lj01-09
Set 32 lh01-01, lh01-02
Set 33 lh02-01, lh02-02
Set 34 lh03-01, lh03-02, lh03-03
Set 35 lh04-01, lh04-02
Set 36 lh05-01, lh05-02, lh05-03
Set 37 li01-01, li01-02, li01-03
Case Name Status Exec Time Memory
la01-01 AC 190 ms 58840 KB
la01-02 AC 118 ms 42688 KB
la01-03 AC 122 ms 42996 KB
la01-04 AC 125 ms 42928 KB
la02-01 AC 110 ms 42604 KB
la02-02 AC 115 ms 42216 KB
lb01-01 AC 372 ms 69764 KB
lb01-02 AC 156 ms 49208 KB
lb01-03 AC 151 ms 49200 KB
lb02-01 AC 132 ms 42956 KB
lb02-02 AC 120 ms 43248 KB
lc01-01 AC 144 ms 49352 KB
lc01-02 AC 120 ms 42684 KB
lc01-03 AC 118 ms 42668 KB
lc01-04 AC 119 ms 42692 KB
le01-01 AC 118 ms 42976 KB
le01-02 AC 121 ms 42684 KB
le01-03 AC 125 ms 42968 KB
le01-04 AC 127 ms 43004 KB
lh01-01 AC 279 ms 40212 KB
lh01-02 AC 292 ms 40508 KB
lh02-01 AC 290 ms 40408 KB
lh02-02 AC 291 ms 40532 KB
lh03-01 AC 289 ms 40580 KB
lh03-02 AC 292 ms 42604 KB
lh03-03 AC 388 ms 54820 KB
lh04-01 AC 409 ms 55348 KB
lh04-02 AC 293 ms 40240 KB
lh05-01 AC 326 ms 47492 KB
lh05-02 AC 591 ms 69896 KB
lh05-03 AC 248 ms 39736 KB
li01-01 AC 174 ms 74740 KB
li01-02 WA 476 ms 61544 KB
li01-03 AC 243 ms 39712 KB
lj01-01 AC 110 ms 41644 KB
lj01-02 AC 118 ms 41588 KB
lj01-03 AC 118 ms 42212 KB
lj01-04 AC 115 ms 42156 KB
lj01-05 AC 118 ms 41988 KB
lj01-06 AC 126 ms 42384 KB
lj01-07 AC 114 ms 41400 KB
lj01-08 AC 114 ms 41368 KB
lj01-09 AC 428 ms 62736 KB
sa01-01 AC 193 ms 55088 KB
sa01-02 AC 111 ms 41376 KB
sa01-03 AC 115 ms 41416 KB
sa01-04 AC 121 ms 41124 KB
sa01-05 AC 112 ms 41144 KB
sa01-06 AC 114 ms 41500 KB
sa02-01 AC 114 ms 41488 KB
sa02-02 AC 114 ms 41720 KB
sb01-01 AC 277 ms 60832 KB
sb01-02 AC 115 ms 41240 KB
sb01-03 AC 111 ms 41376 KB
sb01-04 AC 116 ms 41192 KB
sb02-01 AC 114 ms 41704 KB
sb02-02 AC 114 ms 41624 KB
sb02-03 AC 113 ms 41464 KB
sb02-04 AC 113 ms 41344 KB
sb02-05 AC 122 ms 41476 KB
sc01-01 AC 185 ms 54896 KB
sc01-02 AC 129 ms 41436 KB
sc02-01 AC 114 ms 41372 KB
sc02-02 AC 116 ms 41416 KB
sc02-03 AC 118 ms 41432 KB
sd01-01 AC 209 ms 55080 KB
sd01-02 AC 113 ms 41356 KB
sd01-03 AC 121 ms 41312 KB
sd01-04 AC 111 ms 41492 KB
sd01-05 AC 118 ms 41156 KB
sd01-06 AC 114 ms 41172 KB
sd02-01 AC 122 ms 41588 KB
sd02-02 AC 116 ms 41344 KB
sd02-03 AC 115 ms 41280 KB
sd02-04 AC 122 ms 41368 KB
sd02-05 AC 109 ms 41224 KB
se01-01 AC 134 ms 41128 KB
se01-02 AC 110 ms 41360 KB
se01-03 AC 118 ms 41496 KB
se01-04 AC 125 ms 41428 KB
se01-05 AC 116 ms 41188 KB
se02-01 AC 174 ms 55352 KB
se02-02 AC 116 ms 41212 KB
se02-03 AC 121 ms 41112 KB
se02-04 AC 118 ms 41584 KB
se02-05 AC 113 ms 41224 KB
sf01-01 AC 114 ms 41372 KB
sf01-02 AC 119 ms 41504 KB
sf01-03 AC 117 ms 41436 KB
sf01-04 AC 163 ms 54860 KB
sf02-01 AC 175 ms 59692 KB
sf02-02 AC 113 ms 41176 KB
sf02-03 AC 122 ms 41172 KB
sg01-01 AC 110 ms 41412 KB
sg01-02 AC 126 ms 41612 KB
sg01-03 AC 117 ms 41560 KB
sg01-04 AC 110 ms 41400 KB
sg01-05 AC 113 ms 41352 KB
sg01-06 AC 120 ms 41572 KB
sg01-07 AC 114 ms 41408 KB
sg01-08 AC 120 ms 41516 KB
sh01-01 AC 279 ms 40240 KB
sh02-01 WA 281 ms 40244 KB
sh03-01 AC 274 ms 40348 KB
sh04-01 AC 283 ms 40512 KB
sh05-01 AC 364 ms 50764 KB
sh06-01 AC 373 ms 54656 KB
sh07-01 AC 381 ms 52452 KB
sh08-01 AC 412 ms 55356 KB
sh09-01 AC 485 ms 61472 KB
sh10-01 AC 597 ms 69440 KB
sh10-02 AC 245 ms 39624 KB
sh10-03 AC 244 ms 39788 KB
si01-01 AC 178 ms 74720 KB
si01-02 AC 252 ms 39996 KB