#686553 (C#) No.1640 簡単な色塗り

• 問題: No.1640 簡単な色塗り
• ユーザー: yupiteru_kun
• 提出日時: 2021-08-06 21:59:21
• 言語: C# (.NET 8.0.404)
• 結果: TLE
• 実行時間: -
• コード長: 17,504 bytes
• コンパイル時間: 14,689 ms
• コンパイル使用メモリ: 167,396 KB
• 実行使用メモリ: 175,324 KB
• 最終ジャッジ日時: 2024-06-29 15:07:44
• 合計ジャッジ時間: 30,839 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
sample	AC * 3
other	AC * 28 TLE * 1 -- * 24

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (96 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using static System.Math;
using System.Text;
using System.Threading;
using System.Globalization;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using Library;

namespace Program
{
    public static class ProblemE
    {
        static bool SAIKI = false;
        static public int numberOfRandomCases = 0;
        static public void MakeTestCase(List<string> _input, List<string> _output, ref Func<string[], bool> _outputChecker)
        {
        }
        static public void Solve()
        {
            var N = NN;
            var AB = Repeat(0, N).Select(_ => new { A = NN - 1, B = NN - 1 }).ToArray();
            var bs1 = 0L;
            var bs2 = N;
            var gs = bs2 + N;
            var st = gs + N;
            var go = st + 1;
            var flow = new LIB_MaxFlow(go + 1);
            for (var i = 0; i < N; ++i)
            {
                flow.AddEdge(st, bs1 + i, 1);
                flow.AddEdge(bs1 + i, bs2 + AB[i].A, 1);
                flow.AddEdge(bs1 + i, bs2 + AB[i].B, 1);
                flow.AddEdge(bs2 + i, gs + i, 1);
                flow.AddEdge(gs + i, go, 1);
            }
            var cnt = flow.Flow(st, go);
            if (cnt < N) Console.WriteLine("No");
            else
            {
                Console.WriteLine("Yes");
                var ans = new long[N];
                foreach (var item in flow.GetAllEdge())
                {
                    if (item.from >= bs1 && item.from < bs2 && item.flow == 1)
                    {
                        ans[item.from - bs1] = item.to - bs2;
                    }
                }
                for (var i = 0; i < N; ++i)
                {
                    Console.WriteLine(ans[i] + 1);
                }
            }
        }
        class Printer : StreamWriter
        {
            public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
            public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { base.AutoFlush = false; }
            public Printer(Stream stream, Encoding encoding) : base(stream, encoding) { base.AutoFlush = false; }
        }
        static LIB_FastIO fastio = new LIB_FastIODebug();
        static public void Main(string[] args) { if (args.Length == 0) { fastio = new LIB_FastIO(); Console.SetOut(new Printer(Console.OpenStandardOutput())); } if (SAIKI) { var t = new Thread(Solve, 134217728); t.Start(); t.Join(); } else Solve(); Console.Out.Flush(); }
        static long NN => fastio.Long();
        static double ND => fastio.Double();
        static string NS => fastio.Scan();
        static long[] NNList(long N) => Repeat(0, N).Select(_ => NN).ToArray();
        static double[] NDList(long N) => Repeat(0, N).Select(_ => ND).ToArray();
        static string[] NSList(long N) => Repeat(0, N).Select(_ => NS).ToArray();
        static long Count<T>(this IEnumerable<T> x, Func<T, bool> pred) => Enumerable.Count(x, pred);
        static IEnumerable<T> Repeat<T>(T v, long n) => Enumerable.Repeat<T>(v, (int)n);
        static IEnumerable<int> Range(long s, long c) => Enumerable.Range((int)s, (int)c);
        static IOrderedEnumerable<T> OrderByRand<T>(this IEnumerable<T> x) => Enumerable.OrderBy(x, _ => xorshift);
        static IOrderedEnumerable<T> OrderBy<T>(this IEnumerable<T> x) => Enumerable.OrderBy(x.OrderByRand(), e => e);
        static IOrderedEnumerable<T1> OrderBy<T1, T2>(this IEnumerable<T1> x, Func<T1, T2> selector) => Enumerable.OrderBy(x.OrderByRand(), selector);
        static IOrderedEnumerable<T> OrderByDescending<T>(this IEnumerable<T> x) => Enumerable.OrderByDescending(x.OrderByRand(), e => e);
        static IOrderedEnumerable<T1> OrderByDescending<T1, T2>(this IEnumerable<T1> x, Func<T1, T2> selector) => Enumerable.OrderByDescending(x.OrderByRand(), selector);
        static IOrderedEnumerable<string> OrderBy(this IEnumerable<string> x) => x.OrderByRand().OrderBy(e => e, StringComparer.OrdinalIgnoreCase);
        static IOrderedEnumerable<T> OrderBy<T>(this IEnumerable<T> x, Func<T, string> selector) => x.OrderByRand().OrderBy(selector, StringComparer.OrdinalIgnoreCase);
        static IOrderedEnumerable<string> OrderByDescending(this IEnumerable<string> x) => x.OrderByRand().OrderByDescending(e => e, StringComparer.OrdinalIgnoreCase);
        static IOrderedEnumerable<T> OrderByDescending<T>(this IEnumerable<T> x, Func<T, string> selector) => x.OrderByRand().OrderByDescending(selector, StringComparer.OrdinalIgnoreCase);
        static string Join<T>(this IEnumerable<T> x, string separator = "") => string.Join(separator, x);
        static uint xorshift { get { _xsi.MoveNext(); return _xsi.Current; } }
        static IEnumerator<uint> _xsi = _xsc();
        static IEnumerator<uint> _xsc() { uint x = 123456789, y = 362436069, z = 521288629, w = (uint)(DateTime.Now.Ticks & 0xffffffff); while (true) { var t = x ^ (x << 11); x = y; y = z; z = w; w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); yield return w; } }
        static bool Chmax<T>(this ref T lhs, T rhs) where T : struct, IComparable<T> { if (lhs.CompareTo(rhs) < 0) { lhs = rhs; return true; } return false; }
        static bool Chmin<T>(this ref T lhs, T rhs) where T : struct, IComparable<T> { if (lhs.CompareTo(rhs) > 0) { lhs = rhs; return true; } return false; }
        static void Fill<T>(this T[] array, T value) => array.AsSpan().Fill(value);
        static void Fill<T>(this T[,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0], array.Length).Fill(value);
        static void Fill<T>(this T[,,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0, 0], array.Length).Fill(value);
        static void Fill<T>(this T[,,,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0, 0, 0], array.Length).Fill(value);
    }
}
namespace Library {
    class LIB_MaxFlow
    {
        public struct Edge
        {
            public int from;
            public int to;
            public long cap;
            public long flow;
        }
        const int SHIFT_SIZE = 30;
        const int MASK = 1073741823;
        ulong[] pos;
        int posCnt;
        int[][] gTo;
        int[] gToCnt;
        int[][] gRev;
        int[] gRevCnt;
        long[][] gCap;
        int[] gCapCnt;
        int N;
        public LIB_MaxFlow(long n)
        {
            N = (int)n;
            pos = new ulong[16];
            gTo = new int[n][];
            gRev = new int[n][];
            gCap = new long[n][];
            gToCnt = new int[n];
            gRevCnt = new int[n];
            gCapCnt = new int[n];
            ref var gToref = ref gTo[0];
            ref var gRevref = ref gRev[0];
            ref var gCapref = ref gCap[0];
            for (var i = 0; i < n; i++)
            {
                Unsafe.Add(ref gToref, i) = new int[16];
                Unsafe.Add(ref gRevref, i) = new int[16];
                Unsafe.Add(ref gCapref, i) = new long[16];
            }
        }
        [MethodImpl(MethodImplOptions.AggressiveOptimization)]
        public int AddEdge(long from, long to, long cap)
        {
            pos[posCnt++] = ((ulong)from << SHIFT_SIZE) | (uint)gToCnt[from];
            gTo[from][gToCnt[from]++] = (int)to;
            gRev[from][gRevCnt[from]++] = gRevCnt[to];
            gCap[from][gCapCnt[from]++] = cap;
            gTo[to][gToCnt[to]++] = (int)from;
            gRev[to][gRevCnt[to]++] = gRevCnt[from] - 1;
            gCap[to][gCapCnt[to]++] = 0;
            if (posCnt == pos.Length)
            {
                var tmp = new ulong[posCnt << 1];
                Unsafe.CopyBlock(ref Unsafe.As<ulong, byte>(ref tmp[0]), ref Unsafe.As<ulong, byte>(ref pos[0]), (uint)(8 * posCnt));
                pos = tmp;
            }
            if (gToCnt[from] == gTo[from].Length)
            {
                {
                    var tmp = new int[gToCnt[from] << 1];
                    Unsafe.CopyBlock(ref Unsafe.As<int, byte>(ref tmp[0]), ref Unsafe.As<int, byte>(ref gTo[from][0]), (uint)(4 * gToCnt[from]));
                    gTo[from] = tmp;
                }
                {
                    var tmp = new int[gRevCnt[from] << 1];
                    Unsafe.CopyBlock(ref Unsafe.As<int, byte>(ref tmp[0]), ref Unsafe.As<int, byte>(ref gRev[from][0]), (uint)(4 * gRevCnt[from]));
                    gRev[from] = tmp;
                }
                {
                    var tmp = new long[gCapCnt[from] << 1];
                    Unsafe.CopyBlock(ref Unsafe.As<long, byte>(ref tmp[0]), ref Unsafe.As<long, byte>(ref gCap[from][0]), (uint)(8 * gCapCnt[from]));
                    gCap[from] = tmp;
                }
            }
            if (gToCnt[to] == gTo[to].Length)
            {
                {
                    var tmp = new int[gToCnt[to] << 1];
                    Unsafe.CopyBlock(ref Unsafe.As<int, byte>(ref tmp[0]), ref Unsafe.As<int, byte>(ref gTo[to][0]), (uint)(4 * gToCnt[to]));
                    gTo[to] = tmp;
                }
                {
                    var tmp = new int[gRevCnt[to] << 1];
                    Unsafe.CopyBlock(ref Unsafe.As<int, byte>(ref tmp[0]), ref Unsafe.As<int, byte>(ref gRev[to][0]), (uint)(4 * gRevCnt[to]));
                    gRev[to] = tmp;
                }
                {
                    var tmp = new long[gCapCnt[to] << 1];
                    Unsafe.CopyBlock(ref Unsafe.As<long, byte>(ref tmp[0]), ref Unsafe.As<long, byte>(ref gCap[to][0]), (uint)(8 * gCapCnt[to]));
                    gCap[to] = tmp;
                }
            }
            return posCnt - 1;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public Edge GetEdge(long i)
        {
            var idx = (int)i;
            var idxf = pos[idx] >> SHIFT_SIZE;
            var idxt = (int)(pos[idx] & MASK);
            var eTo = gTo[idxf][idxt];
            var eRev = gRev[idxf][idxt];
            var reCap = gCap[eTo][eRev];
            return new Edge { from = (int)(pos[idx] >> SHIFT_SIZE), to = eTo, cap = gCap[idxf][idxt] + reCap, flow = reCap };
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public Edge[] GetAllEdge()
        {
            var res = new Edge[posCnt];
            for (var i = 0; i < res.Length; ++i) res[i] = GetEdge(i);
            return res;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void ChangeEdge(long i, long newCap, long newFlow)
        {
            var idx = (int)i;
            var idxf = pos[idx] >> SHIFT_SIZE;
            var idxt = (int)(pos[idx] & MASK);
            gCap[idxf][idxt] = newCap - newFlow;
            gCap[gTo[idxf][idxt]][gRev[idxf][idxt]] = newFlow;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public long Flow(long s, long t) => Flow(s, t, long.MaxValue >> 2);
        [MethodImpl(MethodImplOptions.AggressiveOptimization)]
        public long Flow(long s, long t, long flowLimit)
        {
            int si = (int)s;
            int ti = (int)t;
            var level = new int[N];
            var iter = new int[N];
            ref var iterref = ref iter[0];
            Func<int, long, long> dfs = null;
            dfs = (v, up) =>
            {
                var res = 0L;
                ref var levelref = ref level[0];
                ref var gToVref = ref gTo[v][0];
                ref var gCapref = ref gCap[0];
                ref var gCapVref = ref gCap[v][0];
                ref var gRevVref = ref gRev[v][0];
                var levelv = Unsafe.Add(ref levelref, v);
                ref var iterv = ref iter[v];
                var gToCntV = gToCnt[v];
                for (; iterv < gToCntV; ++iterv)
                {
                    var gToVi = Unsafe.Add(ref gToVref, iterv);
                    var gRevVi = Unsafe.Add(ref gRevVref, iterv);
                    var gcap = Unsafe.Add(ref gCapref, gToVi)[gRevVi];
                    if (levelv <= Unsafe.Add(ref levelref, gToVi) || gcap == 0) continue;
                    var param = Math.Min(up - res, gcap);
                    var d = gToVi == si ? param : dfs(gToVi, param);
                    if (d <= 0) continue;
                    Unsafe.Add(ref gCapVref, iterv) += d;
                    Unsafe.Add(ref gCapref, gToVi)[gRevVi] -= d;
                    res += d;
                    if (res == up) break;
                }
                return res;
            };
            var flow = 0L;
            ref var levelref = ref level[0];
            var que = new Queue<int>();
            while (flow < flowLimit)
            {
                Unsafe.InitBlock(ref Unsafe.As<int, byte>(ref levelref), 255, (uint)N << 2);
                Unsafe.Add(ref levelref, si) = 0;
                que.Enqueue(si);
                while (que.Count > 0)
                {
                    var v = que.Dequeue();
                    ref var gToVref = ref gTo[v][0];
                    ref var gCapVref = ref gCap[v][0];
                    var levelv = Unsafe.Add(ref levelref, v) + 1;
                    for (var i = 0; i < gToCnt[v]; ++i)
                    {
                        var gToVi = Unsafe.Add(ref gToVref, i);
                        if (Unsafe.Add(ref gCapVref, i) == 0 || Unsafe.Add(ref levelref, gToVi) >= 0) continue;
                        Unsafe.Add(ref levelref, gToVi) = levelv;
                        if (gToVi == ti)
                        {
                            que.Clear();
                            break;
                        }
                        que.Enqueue(gToVi);
                    }
                }
                if (Unsafe.Add(ref levelref, ti) == -1) break;
                Unsafe.InitBlock(ref Unsafe.As<int, byte>(ref iterref), 0, (uint)N << 2);
                while (flow < flowLimit)
                {
                    var f = ti == si ? (flowLimit - flow) : dfs(ti, flowLimit - flow);
                    if (f == 0) break;
                    flow += f;
                }
            }
            return flow;
        }
        [MethodImpl(MethodImplOptions.AggressiveOptimization)]
        public bool[] MinCut(long s)
        {
            var visited = new bool[N];
            var que = new Queue<int>();
            que.Enqueue((int)s);
            while (que.Count > 0)
            {
                var p = que.Dequeue();
                visited[p] = true;
                var gToP = gTo[p];
                var gCapP = gCap[p];
                for (var i = 0; i < gToCnt[p]; ++i)
                {
                    var gToPi = gToP[i];
                    if (gCapP[i] > 0 && !visited[gToPi])
                    {
                        visited[gToPi] = true;
                        que.Enqueue(gToPi);
                    }
                }
            }
            return visited;
        }
    }
    class LIB_FastIO
    {
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public LIB_FastIO() { str = Console.OpenStandardInput(); }
        readonly Stream str;
        readonly byte[] buf = new byte[2048];
        int len, ptr;
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        byte read()
        {
            if (ptr >= len)
            {
                ptr = 0;
                if ((len = str.Read(buf, 0, 2048)) <= 0)
                {
                    return 0;
                }
            }
            return buf[ptr++];
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        char Char()
        {
            byte b = 0;
            do b = read();
            while (b < 33 || 126 < b);
            return (char)b;
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        virtual public string Scan()
        {
            var sb = new StringBuilder();
            for (var b = Char(); b >= 33 && b <= 126; b = (char)read())
                sb.Append(b);
            return sb.ToString();
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        virtual public long Long()
        {
            long ret = 0; byte b = 0; var ng = false;
            do b = read();
            while (b != '-' && (b < '0' || '9' < b));
            if (b == '-') { ng = true; b = read(); }
            for (; true; b = read())
            {
                if (b < '0' || '9' < b)
                    return ng ? -ret : ret;
                else ret = (ret << 3) + (ret << 1) + b - '0';
            }
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        virtual public double Double() { return double.Parse(Scan(), CultureInfo.InvariantCulture); }
    }
    class LIB_FastIODebug : LIB_FastIO
    {
        Queue<string> param = new Queue<string>();
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        string NextString() { if (param.Count == 0) foreach (var item in Console.ReadLine().Split(' ')) param.Enqueue(item); return param.Dequeue(); }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public LIB_FastIODebug() { }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public override string Scan() => NextString();
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public override long Long() => long.Parse(NextString());
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public override double Double() => double.Parse(NextString());
    }
}