結果

問題 No.2780 The Bottle Imp
コンテスト
ユーザー tobisatis
提出日時 2024-06-07 23:29:22
言語 C#
(.NET 8.0.404)
結果
TLE  
実行時間 -
コード長 7,954 bytes
コンパイル時間 13,063 ms
コンパイル使用メモリ 167,740 KB
実行使用メモリ 96,000 KB
最終ジャッジ日時 2024-12-27 14:39:16
合計ジャッジ時間 26,856 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 39 TLE * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (130 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/

ソースコード

diff # 

namespace AtCoder;

#nullable enable

using System.Numerics;

class Graph<T>
{
    public struct Edge
    {
        public int Ab { get; set; }
        public int Ad { get; set; }
        public T Distance { get; set; }
    }

    public int N { get; private init; }
    public bool Directed { get; private init; }
    public List<List<(int next, int edgeIndex)>> AdjacencyList { get; private init; }
    public List<Edge> Edges { get; private init; }

    public Graph(int verticals, IReadOnlyList<Edge> edges, bool directed)
    {
        N = verticals;
        Directed = directed;
        AdjacencyList = new List<List<(int, int)>>();
        for (var i = 0; i < N; i++) AdjacencyList.Add(new List<(int, int)>());
        Edges = new List<Edge>();
        for (var i = 0; i < edges.Count; i++)
        {
            var edge = edges[i];
            Edges.Add(edge);
            AdjacencyList[edge.Ab].Add((edge.Ad, i));
            if (!Directed) AdjacencyList[edge.Ad].Add((edge.Ab, i));
        }
    }
}

class GraphBuilder
{
    public static Graph<int> SimpleGraph(int verticals, (int ab, int ad)[] edges, bool directed)
    {
        var e = edges.Select(e => new Graph<int>.Edge { Ab = e.ab, Ad = e.ad, Distance = 1 }).ToList();
        return new(verticals, e, directed);
    }

    public static Graph<T> Graph<T>(int verticals, (int ab, int ad, T edge)[] edges, bool directed)
    {
        var e = edges.Select(e => new Graph<T>.Edge { Ab = e.ab, Ad = e.ad, Distance = e.edge }).ToList();
        return new(verticals, e, directed);
    }
}

class GraphBase<T> { public required Graph<T> Graph { get; init; } }

class DirectedGraph<T> : GraphBase<T>
{
    public static DirectedGraph<T>? TryConstruct(Graph<T> graph)
    {
        if (!graph.Directed) return null;
        return new DirectedGraph<T> { Graph = graph };
    }
}

static class DirectedGraphExtensions
{
    public static int[] StronglyConnectedComponents<T>(this DirectedGraph<T> graph)
    {
        var Graph = graph.Graph;
        var n = Graph.N;
        var orders = new int[n];
        var lowLinks = new int[n];
        var roots = new int[n];
        for (var i = 0; i < n; i++) (orders[i], lowLinks[i], roots[i]) = (n, n, n);
        var order = 0;
        bool Visited(int v) => orders[v] != n;
        var stack = new Stack<int>();
        void S(int v)
        {
            orders[v] = lowLinks[v] = order++;
            stack.Push(v);
            foreach (var (next, _) in Graph.AdjacencyList[v])
            {
                if (!Visited(next))
                {
                    S(next);
                    lowLinks[v] = Math.Min(lowLinks[v], lowLinks[next]);
                }
                else if (roots[next] == n) lowLinks[v] = Math.Min(lowLinks[v], orders[next]);
            }
            if (orders[v] == lowLinks[v])
            {
                var u = v;
                while ((u = stack.Pop()) != v) roots[u] = v;
                roots[v] = v;
            }
        }
        for (var i = 0; i < n; i++) if (!Visited(i)) S(i);
        return roots;
    }
}

class DynamicDirectedGraph
{
    List<(int Ab, int Ad, bool Deleted)> Edges { get; init; } = new();
    public HashSet<int>[] AI { get; init; }
    public HashSet<int>[] AO { get; init; }
    public List<HashSet<int>> DI { get; init; }
    public List<HashSet<int>> DO { get; init; }

    public DynamicDirectedGraph(int n)
    {
        {
            var a = new HashSet<int>[n];
            for (var i = 0; i < n; i++) a[i] = new();
            AI = a;
        }
        {
            var a = new HashSet<int>[n];
            for (var i = 0; i < n; i++) a[i] = new();
            AO = a;
        }
        {
            var s = new HashSet<int>();
            for (var j = 0; j < n; j++) s.Add(j);
            var d = new List<HashSet<int>>{ s };
            DI = d;
        }
        {
            var s = new HashSet<int>();
            for (var j = 0; j < n; j++) s.Add(j);
            var d = new List<HashSet<int>>{ s };
            DO = d;
        }
    }

    public int AddEdge(int ab, int ad)
    {
        if (ab == ad || AO[ab].Contains(ad)) return -1;
        Edges.Add((ab, ad, false));
        var e = Edges.Count - 1;
        UCI(ad, 1);
        AI[ad].Add(e);
        UCO(ab, 1);
        AO[ab].Add(e);
        return e;
    }

    public void RemoveEdge(int edge)
    {
        var (ab, ad, deleted) = Edges[edge];
        if (deleted) return;
        Edges[edge] = (ab, ad, true);
        UCI(ad, -1);
        AI[ad].Remove(edge);
        UCO(ab, -1);
        AO[ab].Remove(edge);
    }

    public void RemoveNode(int node)
    {
        var (ez, ai, ao) = (Edges, AI, AO);
        var (ei, eo) = (ai[node], ao[node]);
        var (ci, co) = (ei.Count, eo.Count);
        foreach (var e in ei)
        {
            var ab = ez[e].Ab;
            UCO(ab, -1);
            ao[ab].Remove(e);
            ez[e] = (ab, node, true);
        }
        foreach (var e in eo)
        {
            var ad = ez[e].Ad;
            UCI(ad, -1);
            ai[ad].Remove(e);
            ez[e] = (node, ad, true);
        }
        UCI(node, -ci);
        UCO(node, -co);
    }

    static void UD(HashSet<int>[] a, List<HashSet<int>> d, int v, int diff)
    {
        var current = a[v].Count;
        d[current].Remove(v);
        while (current + diff >= d.Count) d.Add(new());
        d[current + diff].Add(v);
    }
    void UCI(int v, int diff) => UD(AI, DI, v, diff);
    void UCO(int v, int diff) => UD(AO, DO, v, diff);
}

static class Extensions
{
    public static T[] Repeat<T>(this int time, Func<T> F) => Enumerable.Range(0, time).Select(_ => F()).ToArray();
}

class AtCoder
{
    object? Solve()
    {
        var n = Int();
        var edges = new List<(int, int)>();
        for (var i = 0; i < n; i++)
        {
            var str = Console.ReadLine()!.Trim().Split(' ');
            var m = int.Parse(str[0]);
            for (var j = 1; j <= m; j++)
            {
                var a = int.Parse(str[j]) - 1;
                edges.Add((i, a));
            }
        }
        var g = GraphBuilder.SimpleGraph(n, edges.ToArray(), true);
        var scc = DirectedGraph<int>.TryConstruct(g)!.StronglyConnectedComponents();
        var dg = new DynamicDirectedGraph(n);
        foreach (var (u, v) in edges)
        {
            var ab = scc[u];
            var ad = scc[v];
            dg.AddEdge(ab, ad);
        }
        for (var i = 0; i < n; i++) if (scc[i] != i) dg.DO[0].Remove(i);
        while (true)
        {
            if (dg.DO[0].Count == 0) return true;
            if (dg.DO[0].Count > 1) return false;
            var v = dg.DO[0].First();
            dg.RemoveNode(v);
            dg.DO[0].Remove(v);
            if (v == scc[0]) break;
        }
        return dg.DO[0].Count == 0;
    }

    public static void Main() => new AtCoder().Run();
    public void Run()
    {
        var res = Solve();
        if (res != null)
        {
            if (res is bool yes) res = yes ? "Yes" : "No";
            sw.WriteLine(res);
        }
        sw.Flush();
    }

    string[] input = Array.Empty<string>();
    int iter = 0;
    readonly StreamWriter sw = new(Console.OpenStandardOutput()) { AutoFlush = false };

    string String()
    {
        while (iter >= input.Length) (input, iter) = (Console.ReadLine()!.Split(' '), 0);
        return input[iter++];
    }
    T Input<T>() where T : IParsable<T> => T.Parse(String(), null);
    int Int() => Input<int>();
    void Out(object? x, string? separator = null)
    {
        separator ??= Environment.NewLine;
        if (x is System.Collections.IEnumerable obj and not string)
        {
            var firstLine = true;
            foreach (var item in obj)
            {
                if (!firstLine) sw.Write(separator);
                firstLine = false;
                sw.Write(item);
            }
        }
        else sw.Write(x);
        sw.WriteLine();
    }
}
0