結果
問題 | No.2664 Prime Sum |
ユーザー | crimsontea |
提出日時 | 2024-03-08 21:42:47 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 17,062 bytes |
コンパイル時間 | 7,054 ms |
コンパイル使用メモリ | 168,060 KB |
実行使用メモリ | 191,764 KB |
最終ジャッジ日時 | 2024-09-29 19:17:07 |
合計ジャッジ時間 | 9,844 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 37 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (83 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) /home/judge/data/code/Main.cs(67,32): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(68,30): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj] main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using A;using System.Buffers;using System.Collections;using System.Diagnostics;using System.Numerics;using System.Runtime.CompilerServices;using static A.InputUtility;class Program{static void Main(){using Output output = new(true);InputNewLine();var (n, m) = (NextInt32, NextInt32);List<int>[] graph = new List<int>[n];for (int i = 0; i < graph.Length; i++){graph[i] = new();}for (int i = 0; i < m; i++){InputNewLine();var (u, v) = (NextInt32 - 1, NextInt32 - 1);graph[u].Add(v);graph[v].Add(u);}int[] colors = Enumerable.Repeat(-1, n).ToArray();for (int i = 0; i < n; i++){if (colors[i] == -1){Dfs(i, -1, 0);}}Console.WriteLine("Yes");void Dfs(int cur, int prev , int col){if (colors[cur] != -1){if (colors[cur] != col){Console.WriteLine("No");Environment.Exit(0);}return;}colors[cur] = col;foreach (var next in graph[cur]){Dfs(next, cur, (col + 1) & 1);}}}}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 DEBUGprivate static TextReader? s_textReader;public static void SetSource(string path) => s_textReader = new StringReader(File.ReadAllText(path));#endifpublic static bool InputNewLine(){#if DEBUGif (s_textReader is TextReader sr){Init();s_raw = sr.ReadLine()!;s_inputs = s_raw.Split(' ', StringSplitOptions.RemoveEmptyEntries);return true;}#endifInit();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 DEBUGpublic Output(string path){var fs = new FileStream(path, FileMode.Create, FileAccess.Write);_sw = new StreamWriter(fs);Console.SetOut(_sw);}#endifpublic 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/SourceExpandernamespace 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