結果
| 問題 | No.2630 Colorful Vertices and Cheapest Paths |
| ユーザー |
 crimsontea
|
| 提出日時 | 2024-02-16 23:09:14 |
| 言語 | C# (.NET 8.0.203) |
| 結果 |
AC
|
| 実行時間 | 622 ms / 2,500 ms |
| コード長 | 22,020 bytes |
| コンパイル時間 | 9,966 ms |
| コンパイル使用メモリ | 158,628 KB |
| 実行使用メモリ | 210,780 KB |
| 最終ジャッジ日時 | 2024-02-16 23:10:03 |
| 合計ジャッジ時間 | 21,080 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 247 ms
45,604 KB |
| testcase_01 | AC | 508 ms
58,532 KB |
| testcase_02 | AC | 551 ms
58,916 KB |
| testcase_03 | AC | 92 ms
34,724 KB |
| testcase_04 | AC | 122 ms
34,724 KB |
| testcase_05 | AC | 93 ms
34,724 KB |
| testcase_06 | AC | 356 ms
42,404 KB |
| testcase_07 | AC | 514 ms
59,044 KB |
| testcase_08 | AC | 528 ms
58,916 KB |
| testcase_09 | AC | 486 ms
59,300 KB |
| testcase_10 | AC | 593 ms
59,300 KB |
| testcase_11 | AC | 595 ms
59,172 KB |
| testcase_12 | AC | 619 ms
59,300 KB |
| testcase_13 | AC | 567 ms
59,172 KB |
| testcase_14 | AC | 622 ms
59,172 KB |
| testcase_15 | AC | 466 ms
38,820 KB |
| testcase_16 | AC | 438 ms
38,820 KB |
| testcase_17 | AC | 485 ms
38,820 KB |
| testcase_18 | AC | 362 ms
49,316 KB |
| testcase_19 | AC | 495 ms
58,788 KB |
| testcase_20 | AC | 422 ms
58,788 KB |
| testcase_21 | AC | 482 ms
210,780 KB |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (100 ms)。 MSBuild のバージョン 17.7.3+8ec440e68 (.NET) /home/judge/data/code/Main.cs(102,32): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(103,30): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj] main -> /home/judge/data/code/bin/Release/net7.0/main.dll main -> /home/judge/data/code/bin/Release/net7.0/publish/
ソースコード
using A;
using AtCoder;
using AtCoder.Internal;
using SourceExpander;
using System;
using System.Buffers;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Numerics;
using System.Runtime.CompilerServices;
using static A.InputUtility;
class Program
{
static void Main()
{
using Output output = new(false);
InputNewLine();
var (n, m) = (NextInt32, NextInt32);
var edges = new (int, int)[m];
for (int i = 0; i < edges.Length; i++)
{
InputNewLine();
edges[i] = (NextInt32 - 1, NextInt32 - 1);
}
InputNewLine();
var c = GetInt32Array().Select(x => x - 1).ToArray();
var groups = new List<int>[10];
for (int i = 0; i < groups.Length; i++)
{
groups[i] = new();
}
for (int i = 0; i < c.Length; i++)
{
groups[c[i]].Add(i);
}
InputNewLine();
var w = GetInt64Array();
InputNewLine();
var q = NextInt32;
var queries = new (int, int)[q];
for (int i = 0; i < q; i++)
{
InputNewLine();
queries[i] = (NextInt32 - 1, NextInt32 - 1);
}
long[] res = Enumerable.Repeat(long.MaxValue, q).ToArray();
bool[] enabled = new bool[n];
for (int i = 1; i < 1 << 10; i++)
{
Array.Clear(enabled);
Dsu dsu = new(n);
long cost = 0;
for (int k = 0; k < 10; k++)
{
if (((i >> k) & 1) == 1)
{
cost += w[k];
foreach (var item in groups[k])
{
enabled[item] = true;
}
}
}
foreach (var (u, v) in edges)
{
if (enabled[u] && enabled[v])
{
dsu.Merge(u, v);
}
}
foreach (var (edge, index) in queries.Enumerate())
{
var (u, v) = edge;
if (enabled[u] && enabled[v] && dsu.Same(u, v))
{
res[index] = Math.Min(res[index], cost);
}
}
}
foreach (var cost in res)
{
Console.WriteLine(cost == long.MaxValue ? -1 : cost);
}
}
}
namespace A
{
public static class InputUtility
{
private static string[]? s_inputs;
private static string? s_raw;
private static int s_index = 0;
private static void Init() => s_index = 0;
public static int NextInt32 => int.Parse(s_inputs![s_index++]!);
public static uint NextUInt32 => uint.Parse(s_inputs![s_index++]!);
public static long NextInt64 => long.Parse(s_inputs![s_index++]!);
public static ulong NextUInt64 => ulong.Parse(s_inputs![s_index++]!);
public static string NextString => s_inputs![s_index++];
public static char NextChar => s_inputs![s_index++][0];
public static decimal NextDecimal => decimal.Parse(s_inputs![s_index++]!);
public static BigInteger NextBigInteger => BigInteger.Parse(s_inputs![s_index++]!);
public static int[] GetInt32Array() => s_inputs!.Select(int.Parse).ToArray();
public static long[] GetInt64Array() => s_inputs!.Select(long.Parse).ToArray();
public static string GetRawString() => s_raw!;
#if DEBUG
private static TextReader? s_textReader;
public static void SetSource(string path) => s_textReader = new StringReader(File.ReadAllText(path));
#endif
public static bool InputNewLine()
{
#if DEBUG
if (s_textReader is TextReader sr)
{
Init();
s_raw = sr.ReadLine()!;
s_inputs = s_raw.Split(' ', StringSplitOptions.RemoveEmptyEntries);
return true;
}
#endif
Init();
s_raw = Console.ReadLine()!;
s_inputs = s_raw.Split(' ', StringSplitOptions.RemoveEmptyEntries);
return true;
}
}
public static class CombinationFunction
{
public static void PartedRotate<T>(T[] a, int first1, int last1, int first2, int last2)
{
if (first1 == last1 || first2 == last2) return;
int next = first2;
while (first1 != next)
{
Swap(a, first1++, next++);
if (first1 == last1) first1 = first2;
if (next == last2)
{
next = first2;
}
else if (first1 == first2)
{
first2 = next;
}
}
}
public static bool NextCombinationImp<T>(T[] a, int first1, int last1, int first2, int last2) where T : IComparable<T>
{
if (first1 == last1 || first2 == last2) return false;
int target = last1 - 1;
int lastElem = last2 - 1;
while (target != first1 && !(a[target].CompareTo(a[lastElem]) < 0)) target--;
if (target == first1 && !(a[target].CompareTo(a[lastElem]) < 0))
{
PartedRotate(a, first1, last1, first2, last2);
return false;
}
int next = first2;
while (!(a[target].CompareTo(a[next]) < 0)) next++;
Swap(a, target++, next++);
PartedRotate(a, target, last1, next, last2);
return true;
}
public static bool NextCombination<T>(T[] a, int first, int mid, int last) where T : IComparable<T>
=> NextCombinationImp(a, first, mid, mid, last);
public static bool PrevCombination<T>(T[] a, int first, int mid, int last) where T : IComparable<T>
=> NextCombinationImp(a, mid, last, first, mid);
public static void Swap<T>(T[] a, int i, int j) => (a[i], a[j]) = (a[j], a[i]);
}
public static class PermutationFunction
{
public static bool NextPermutation<T>(T[] a) where T : IComparable<T>
{
int n = a.Length;
int i = n - 2;
while (i >= 0 && a[i].CompareTo(a[i + 1]) >= 0) { i--; }
if (i < 0) { return false; }
int j = n - 1;
while (a[j].CompareTo(a[i]) <= 0) { j--; }
(a[i], a[j]) = (a[j], a[i]);
Array.Reverse(a, i + 1, n - i - 1);
return true;
}
}
public readonly struct Output : IDisposable
{
private readonly StreamWriter _sw;
#if DEBUG
public Output(string path)
{
var fs = new FileStream(path, FileMode.Create, FileAccess.Write);
_sw = new StreamWriter(fs);
Console.SetOut(_sw);
}
#endif
public Output(bool autoFlush)
{
_sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = autoFlush };
Console.SetOut(_sw);
}
public void Dispose()
{
_sw.Dispose();
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
internal void Flush()
{
_sw.Flush();
}
}
public static class ArrayExtensions
{
public static void Swap<T>(this T[] array, int i, int j) => (array[i], array[j]) = (array[j], array[i]);
public static int LowerBound<T>(this T[] a, T target) where T : IComparable<T>
{
int ok = a.Length;
int ng = -1;
while (Math.Abs(ok - ng) > 1 && (ok + ng) / 2 is int mid)
(ok, ng) = a[mid].CompareTo(target) >= 0 ? (mid, ng) : (ok, mid);
return ok;
}
public static int UpperBound<T>(this T[] a, T target) where T : IComparable<T>
{
int ok = a.Length;
int ng = -1;
while (Math.Abs(ok - ng) > 1 && (ok + ng) / 2 is int mid)
(ok, ng) = a[mid].CompareTo(target) > 0 ? (mid, ng) : (ok, mid);
return ok;
}
public struct IndexedEnumerable<T> : IEnumerable<(T item, int index)>
{
private readonly T[] _a;
private readonly int _startIndex;
public IndexedEnumerable(T[] a, int startIndex = 0)
{
_a = a;
_startIndex = startIndex;
}
public readonly IndexedEnumerator<T> GetEnumerator() => new IndexedEnumerator<T>(_a, _startIndex);
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
IEnumerator<(T item, int index)> IEnumerable<(T item, int index)>.GetEnumerator() => GetEnumerator();
}
public struct IndexedEnumerator<T> : IEnumerator<(T item, int index)>
{
public readonly (T item, int index) Current => (_a[_index], _index + _startIndex);
private int _index;
private int _startIndex;
private T[] _a;
public IndexedEnumerator(T[] a, int startIndex)
{
_index = -1;
_a = a;
_startIndex = startIndex;
}
public bool MoveNext() => ++_index < _a.Length;
readonly object IEnumerator.Current => Current;
public readonly void Dispose() { }
public void Reset() => _index = -1;
}
/// <returns>(T value, int index)</returns>
public static IndexedEnumerable<T> Enumerate<T>(this T[] arr, int startIndex = 0) => new IndexedEnumerable<T>(arr, startIndex);
}
public static class IEnumerableExtensions
{
public static IEnumerable<TSource> Log<TSource>(this IEnumerable<TSource> source)
{
Console.WriteLine(string.Join(' ', source));
return source;
}
public static ScanEnumerable<TSource, TAccumulate> Scan<TSource, TAccumulate>(
this IEnumerable<TSource> source,
TAccumulate seed,
Func<TAccumulate, TSource, TAccumulate> accumulator) where TSource : struct where TAccumulate : struct
{
return new ScanEnumerable<TSource, TAccumulate>(source, accumulator, seed);
}
public static IEnumerable<TAccumulate> ScanExSeed<TSource, TAccumulate>(
this IEnumerable<TSource> source,
TAccumulate seed,
Func<TAccumulate, TSource, TAccumulate> accumulator)
{
var accumulation = new List<TAccumulate>();
var current = seed;
foreach (var item in source)
{
current = accumulator(current, item);
accumulation.Add(current);
}
return accumulation;
}
public readonly struct ScanEnumerable<TSource, TAccumulate> : IEnumerable<TAccumulate> where TSource : struct where TAccumulate : struct
{
private readonly IEnumerable<TSource> _source;
private readonly Func<TAccumulate, TSource, TAccumulate> _accumulator;
private readonly TAccumulate _seed;
public ScanEnumerable(IEnumerable<TSource> source, Func<TAccumulate, TSource, TAccumulate> accumulator, TAccumulate seed)
{
_source = source;
_accumulator = accumulator;
_seed = seed;
}
public readonly ScanEnumerator<TSource, TAccumulate> GetEnumerator() => new(_source, _accumulator, _seed);
readonly IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
readonly IEnumerator<TAccumulate> IEnumerable<TAccumulate>.GetEnumerator() => GetEnumerator();
}
public struct ScanEnumerator<TSource, TAccumulate> : IEnumerator<TAccumulate> where TSource : struct where TAccumulate : struct
{
private readonly Func<TAccumulate, TSource, TAccumulate> _accumulator;
private readonly IEnumerator<TSource> _enumerator;
private TAccumulate _current;
private bool _secondOrLaterElement = false;
public ScanEnumerator(IEnumerable<TSource> source, Func<TAccumulate, TSource, TAccumulate> accumulator, TAccumulate seed)
{
_enumerator = source.GetEnumerator();
_accumulator = accumulator;
_current = seed;
}
public readonly TAccumulate Current => _current;
readonly object IEnumerator.Current => Current;
public readonly void Dispose() { }
public bool MoveNext()
{
if (_secondOrLaterElement)
{
if (_enumerator.MoveNext())
{
_current = _accumulator(_current, _enumerator.Current);
return true;
}
return false;
}
else
{
_secondOrLaterElement = true;
return true;
}
}
public void Reset()
{
throw new NotSupportedException();
}
}
public static IEnumerable<TSource> Scan<TSource>(
this IEnumerable<TSource> source,
Func<TSource, TSource, TSource> accumulator)
{
if (source is null)
throw new ArgumentNullException(paramName: nameof(source));
if (accumulator is null)
throw new ArgumentNullException(paramName: nameof(accumulator));
var accumulation = new List<TSource>();
if (source.Any() is false)
{
return accumulation;
}
var current = source.First();
accumulation.Add(current);
foreach (var item in source.Skip(1))
{
current = accumulator(current, item);
accumulation.Add(current);
}
return accumulation;
}
public static CombinationEnumerable<T> Combination<T>(this T[] a, int k) where T : IComparable<T>
=> new(a, k);
public readonly struct CombinationEnumerable<T> where T : IComparable<T>
{
private readonly T[] _a;
private readonly int _k;
public CombinationEnumerable(T[] a, int k)
{
_a = a;
_k = k;
}
public readonly CombinationEnumerator<T> GetEnumerator() => new(_a, _k);
}
public struct CombinationEnumerator<T> : IEnumerator<ReadOnlyMemory<T>> where T : IComparable<T>
{
private readonly int _k;
private readonly T[] _a;
private readonly int _n;
private bool _secondOrLaterElement = false;
public CombinationEnumerator(T[] a, int k)
{
_a = a;
_n = a.Length;
_k = k;
}
public readonly ReadOnlyMemory<T> Current => _a.AsMemory()[.._k];
readonly object IEnumerator.Current => Current;
public readonly void Dispose() { }
public bool MoveNext()
{
if (_secondOrLaterElement)
{
return CombinationFunction.NextCombination(_a, 0, _k, _n);
}
else
{
_secondOrLaterElement = true;
return true;
}
}
public void Reset()
{
throw new NotSupportedException();
}
}
public static PermutationEnumerable<T> Permutation<T>(this T[] a) where T : IComparable<T> => new(a);
public readonly struct PermutationEnumerable<T> where T : IComparable<T>
{
private readonly T[] _a;
public PermutationEnumerable(T[] a) => _a = a;
public readonly PermutationEnumerator<T> GetEnumerator() => new(_a);
}
public struct PermutationEnumerator<T> : IEnumerator<ReadOnlyMemory<T>> where T : IComparable<T>
{
private readonly T[] _a;
private readonly int _n;
private bool _secondOrLaterElement = false;
public PermutationEnumerator(T[] a)
{
_a = a;
_n = a.Length;
}
public readonly ReadOnlyMemory<T> Current => _a.AsMemory()[..];
readonly object IEnumerator.Current => Current;
public readonly void Dispose() { }
public bool MoveNext()
{
if (_secondOrLaterElement)
{
return PermutationFunction.NextPermutation(_a);
}
else
{
_secondOrLaterElement = true;
return true;
}
}
public void Reset() => throw new NotSupportedException();
}
}
public class MyMath
{
public static long Pow(long x, int y) => Enumerable.Repeat(x, y).Aggregate(1L, (acc, x) => acc * x);
public static long Pow10(int y) => Pow(10, y);
public static long Pow2(int y) => Pow(2, y);
}
public class MyMathBigInteger
{
public static BigInteger Pow(long x, int y) => Enumerable.Repeat(x, y).Aggregate(new BigInteger(1), (acc, x) => acc * x);
public static BigInteger Pow10(int y) => Pow(10, y);
public static BigInteger Pow2(int y) => Pow(2, y);
}
}
#region Expanded by https://github.com/kzrnm/SourceExpander
namespace AtCoder{public class Dsu{public readonly int[]_parentOrSize;public Dsu(int n){_parentOrSize=new int[n];_parentOrSize.AsSpan().Fill(-1);}[MethodImpl(256)]public int Merge(int a,int b){int x=Leader(a),y=Leader(b);if(x==y)return x;if(-_parentOrSize[x]<-_parentOrSize[y])(x,y)=(y,x);_parentOrSize[x]+=_parentOrSize[y];_parentOrSize[y]=x;return x;}[MethodImpl(256)]public bool Same(int a,int b){return Leader(a)==Leader(b);}[MethodImpl(256)]public int Leader(int a){if(_parentOrSize[a]<0)return a;while(0<=_parentOrSize[_parentOrSize[a]]){(a,_parentOrSize[a])=(_parentOrSize[a],_parentOrSize[_parentOrSize[a]]);}return _parentOrSize[a];}[MethodImpl(256)]public int Size(int a){return-_parentOrSize[Leader(a)];}[MethodImpl(256)]public int[][]Groups(){int n=_parentOrSize.Length;int[]leaderBuf=new int[n];int[]id=new int[n];var resultList=new SimpleList<int[]>(n);for(int i=0;i<leaderBuf.Length;i++){leaderBuf[i]=Leader(i);if(i==leaderBuf[i]){id[i]=resultList.Count;resultList.Add(new int[-_parentOrSize[i]]);}}var result=resultList.ToArray();int[]ind=new int[result.Length];for(int i=0;i<leaderBuf.Length;i++){var leaderID=id[leaderBuf[i]];result[leaderID][ind[leaderID]]=i;ind[leaderID]++;}return result;}}}
namespace AtCoder.Internal{public class SimpleList<T>:IList<T>,IReadOnlyList<T>{public 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);}}[MethodImpl(256)]public Memory<T>AsMemory()=>new Memory<T>(data,0,Count);[MethodImpl(256)]public Span<T>AsSpan()=>new Span<T>(data,0,Count);public ref T this[int index]{[MethodImpl(256)]get{if((uint)index>=(uint)Count)ThrowIndexOutOfRangeException();return ref data[index];}}public int Count{get;private set;}[MethodImpl(256)]public void Add(T item){if((uint)Count>=(uint)data.Length)Array.Resize(ref data,data.Length<<1);data[Count++]=item;}[MethodImpl(256)]public void RemoveLast(){if( --Count<0)ThrowIndexOutOfRangeException();}[MethodImpl(256)]public void RemoveLast(int size){if((Count-=size)<0)ThrowIndexOutOfRangeException();}[MethodImpl(256)]public SimpleList<T>Reverse(){Array.Reverse(data,0,Count);return this;}[MethodImpl(256)]public SimpleList<T>Reverse(int index,int count){Array.Reverse(data,index,count);return this;}[MethodImpl(256)]public SimpleList<T>Sort(){Array.Sort(data,0,Count);return this;}[MethodImpl(256)]public SimpleList<T>Sort(IComparer<T>comparer){Array.Sort(data,0,Count,comparer);return this;}[MethodImpl(256)]public SimpleList<T>Sort(int index,int count,IComparer<T>comparer){Array.Sort(data,index,count,comparer);return this;}[MethodImpl(256)]public void Clear()=>Count=0;[MethodImpl(256)]public bool Contains(T item)=>IndexOf(item)>=0;[MethodImpl(256)]public int IndexOf(T item)=>Array.IndexOf(data,item,0,Count);[MethodImpl(256)]public void CopyTo(T[]array,int arrayIndex)=>Array.Copy(data,0,array,arrayIndex,Count);[MethodImpl(256)]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];}[MethodImpl(256)]public Span<T>.Enumerator GetEnumerator()=>AsSpan().GetEnumerator();private static void ThrowIndexOutOfRangeException()=>throw new IndexOutOfRangeException();}}
namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}}
#endregion Expanded by https://github.com/kzrnm/SourceExpander