#179563 (C#(csc)) No.529 帰省ラッシュ

• 問題: No.529 帰省ラッシュ
• ユーザー: eitaho
• 提出日時: 2017-06-11 19:03:21
• 言語: C#(csc) (csc 3.9.0)
• 結果: AC
• 実行時間: 1,035 ms / 4,500 ms
• コード長: 13,829 bytes
• コンパイル時間: 1,988 ms
• コンパイル使用メモリ: 113,536 KB
• 実行使用メモリ: 123,824 KB
• 最終ジャッジ日時: 2024-12-16 07:08:52
• 合計ジャッジ時間: 13,887 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
sample	AC * 2
other	AC * 18

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

using System;
using System.IO;
using System.Linq;
using System.Text;
using System.Collections.Generic;
using System.Diagnostics;
using Enu = System.Linq.Enumerable;

public class Program
{
    public void Solve()
    {
        int N = Reader.Int(), M = Reader.Int(), NQ = Reader.Int();
        var E = Reader.IntTable(M);
        var Q = Reader.IntTable(NQ);
        var comp = new TwoEdgeConnectedComponent(N, E, 1);
        var hld = new HLDecomposition(comp.Count, comp.ComponentEdges);
        var seg = hld.Path.Select(p => new MaxHeapSegmentTree(p.Count)).ToArray();
        var ans = new List<int>();

        foreach (var q in Q)
            if (q[0] == 1)
            {
                int v = comp.VtoComponentId(q[1] - 1), val = q[2];
                seg[hld.Y[v]].Add(hld.X[v], val);
            }
            else
            {
                int a = comp.VtoComponentId(q[1] - 1), b = comp.VtoComponentId(q[2] - 1);
                int maxVal = -1, pathId = 0, index = 0;
                Action<int, int, int> Pop = (p, L, R) =>
                {
                    int v, i;
                    v = seg[p].Max(out i, L, R);
                    if (v > maxVal) { pathId = p; maxVal = v; index = i; }
                };
                hld.Query(a, b, Pop);
                ans.Add(maxVal);
                if (maxVal >= 0) seg[pathId].PopAt(index);
            }

        if (ans.Count > 0) Console.WriteLine(string.Join("\n", ans));
    }
}

public class Component
{
    public List<int> Vertexes;
    public int[] Edges;
    public Component(List<int> vs) { Vertexes = vs; }
}


public class TwoEdgeConnectedComponent
{
    int N, id;
    List<int>[] E;
    int[] VtoCompId, order;
    bool[] inS;
    Stack<int> S = new Stack<int>(), roots = new Stack<int>();
    List<Component> Components = new List<Component>();
    HashSet<long> BridgesSet = new HashSet<long>();
    public List<int[]> Bridges = new List<int[]>();
    public int[][] ComponentEdges;


    public int Count { get { return Components.Count; } }

    public Component this[int i] { get { return Components[i]; } }

    public bool IsBridge(int a, int b) { return BridgesSet.Contains(ToKey(a, b)); }

    public int VtoComponentId(int v) { return VtoCompId[v]; }

    public bool SameComponent(int a, int b) { return VtoCompId[a] == VtoCompId[b]; }

    public TwoEdgeConnectedComponent(int N) { Init(N); }
    public TwoEdgeConnectedComponent(int N, int[][] E, int origin = 0)
    {
        Init(N);
        Array.ForEach(E, e => AddEdge(e[0] - origin, e[1] - origin));
        Decompose();
    }

    void Init(int N)
    {
        this.N = N;
        VtoCompId = new int[N];
        order = new int[N];
        inS = new bool[N];
        E = new List<int>[N];
        for (int i = 0; i < N; i++) E[i] = new List<int>();
    }

    public void AddEdge(int a, int b)
    {
        E[a].Add(b);
        E[b].Add(a);
    }

    public void Decompose()
    {
        for (int i = 0; i < N; i++) if (order[i] == 0) DFS(i);
        CheckEdges();
    }

    void CheckEdges()
    {
        Bridges.Sort((a, b) => a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        var es = new List<int[]>();
        for (int compId = 0; compId < Count; compId++)
        {
            var comp = Components[compId];
            var set = new HashSet<int>();
            foreach (int a in comp.Vertexes)
                foreach (int b in E[a])
                    if (VtoCompId[a] != VtoCompId[b])
                        set.Add(VtoCompId[b]);
            comp.Edges = set.ToArray();
            Array.Sort(comp.Edges);
            foreach (int b in comp.Edges)
                if (compId < b)
                    es.Add(new[] { compId, b });
        }
        ComponentEdges = es.ToArray();
    }

    void DFS(int start)
    {
        var stack = new Stack<int>();
        stack.Push(-1); stack.Push(start);
        for (; stack.Count > 0; )
        {
            int v = stack.Pop(), prev = stack.Pop();
            if (v < 0)
            {
                v = ~v;
                foreach (int next in E[v])
                    if (next != prev && inS[next])
                        while (order[roots.Peek()] > order[next]) roots.Pop();
                if (roots.Peek() != v) continue;
                if (prev != -1) AddBridge(prev, v);
                AddComponent(prev, v);
            }
            else
            {
                if (order[v] != 0) continue;
                stack.Push(prev); stack.Push(~v);
                order[v] = ++id;
                roots.Push(v);
                S.Push(v);
                inS[v] = true;
                foreach (int next in E[v])
                    if (order[next] == 0) { stack.Push(v); stack.Push(next); }
            }
        }
    }

    void AddBridge(int a, int b)
    {
        BridgesSet.Add(ToKey(a, b));
        Bridges.Add(new[] { Math.Min(a, b), Math.Max(a, b) });
    }

    void AddComponent(int prev, int root)
    {
        int compId = Components.Count;
        var vs = new List<int>();
        for (; ; )
        {
            int v = S.Pop();
            inS[v] = false;
            VtoCompId[v] = compId;
            vs.Add(v);
            if (v == root) break;
        }
        vs.Sort();
        Components.Add(new Component(vs));
        roots.Pop();
    }

    long ToKey(long a, long b) { return a < b ? a * N + b : b * N + a; }

}


public class HLDecomposition
{
    int N;
    List<int>[] E;
    public int[] Y, X, Size, Parent, Up, UnderL, UnderR;
    public List<List<int>> Path = new List<List<int>>();
    List<int> PathDepth = new List<int>();


    // F(pathId, L, R)
    public void Query(int a, int b, Action<int, int, int> F)
    {
        for (int at = Y[a], L = 0, R, na = a, nb = b; a != -1; a = na, b = nb)
        {
            if (Y[a] == Y[b]) { at = Y[a]; L = Math.Min(X[a], X[b]); R = Math.Max(X[a], X[b]); na = -1; }
            else if (PathDepth[Y[a]] >= PathDepth[Y[b]]) { at = Y[a]; L = 0; R = X[a]; na = Up[a]; }
            else { at = Y[b]; L = 0; R = X[b]; nb = Up[b]; }
            F(at, L, R + 1);
        }
    }

    public HLDecomposition(int N) { Init(N); }
    public HLDecomposition(int N, int[][] E, int origin = 0)
    {
        Init(N);
        Array.ForEach(E, e => AddEdge(e[0] - origin, e[1] - origin));
        Build();
    }

    void Init(int N)
    {
        this.N = N;
        Y = new int[N]; X = new int[N];
        Size = new int[N]; Parent = new int[N]; Up = new int[N];
        UnderL = new int[N]; UnderR = new int[N];
        E = new List<int>[N];
        for (int i = 0; i < N; i++) E[i] = new List<int>();
    }

    public void AddEdge(int a, int b)
    {
        E[a].Add(b);
        E[b].Add(a);
    }

    public void Build()
    {
        CountNodes();
        CompressPath();
    }

    void CountNodes()
    {
        var stack = new Stack<int>();
        var nodes = new int[N];
        int ni = N - 1;
        stack.Push(0);
        while (stack.Count > 0)
        {
            int a = stack.Pop();
            for (int ei = 0; ei < E[a].Count; ei++)
            {
                int b = E[a][ei];
                if (b == Parent[a]) { E[a].RemoveAt(ei); ei--; }
                else { Parent[b] = a; stack.Push(b); }
            }
            nodes[ni--] = a;
        }
        foreach (int a in nodes)
        {
            Size[a] = 1;
            var e = E[a];
            for (int i = 0; i < e.Count; i++)
            {
                int b = e[i];
                Size[a] += Size[b];
                if (Size[b] > Size[e[0]]) { int t = e[0]; e[0] = b; e[i] = t; }
            }
        }
    }

    void CompressPath()
    {
        var stack = new Stack<int>();
        stack.Push(0);
        while (stack.Count > 0)
        {
            int a = stack.Pop();
            if (a < 0) { UnderR[~a] = Path.Count; continue; }
            if (X[a] == 0)
            {
                Path.Add(new List<int>());
                PathDepth.Add(a == 0 ? 0 : PathDepth[Y[Parent[a]]] + 1);
            }
            int pathId = Y[a] = Path.Count - 1;
            Path[pathId].Add(a);
            Up[a] = Parent[Path[pathId][0]];
            UnderL[a] = Path.Count;
            stack.Push(~a);
            if (E[a].Count == 0) continue;
            for (int i = E[a].Count - 1; i > 0; i--)
                stack.Push(E[a][i]);
            X[E[a][0]] = X[a] + 1;
            stack.Push(E[a][0]);
        }
    }

    public int LCA(int a, int b)
    {
        if (Y[a] == Y[b]) return (X[a] < X[b]) ? a : b;
        if (PathDepth[Y[a]] >= PathDepth[Y[b]])
            return LCA(Parent[Path[Y[a]][0]], b);
        return LCA(a, Parent[Path[Y[b]][0]]);
    }

    public int Dist(int a, int b)
    {
        if (Y[a] == Y[b]) return Math.Abs(X[a] - X[b]);
        if (PathDepth[Y[a]] >= PathDepth[Y[b]])
            return X[a] + 1 + Dist(Parent[Path[Y[a]][0]], b);
        return X[b] + 1 + Dist(a, Parent[Path[Y[b]][0]]);
    }
}


public class MaxHeapSegmentTree
{
    static readonly long[] Q = new long[100];
    public readonly int N;
    readonly int[] Val;
    readonly int[] Who;
    readonly HeapMax[] heap;

    public MaxHeapSegmentTree(int n)
    {
        for (N = 2; N < n; ) N *= 2;
        heap = new HeapMax[N];
        Val = new int[N * 2];
        Who = new int[N * 2];
        for (int i = 0; i < N; i++)
        {
            heap[i] = new HeapMax(2);
            heap[i].Push(int.MinValue);
            Who[N + i] = i;
        }
        for (int i = 0; i < Val.Length; i++) Val[i] = int.MinValue;
    }

    public void Add(int index, int val)
    {
        heap[index].Push(val);
        int i = index + N;
        Val[i] = heap[index].Peek();
        for (i >>= 1; i > 0; i >>= 1)
            if (Val[i << 1] >= Val[i << 1 | 1]) { Val[i] = Val[i << 1]; Who[i] = Who[i << 1]; }
            else { Val[i] = Val[i << 1 | 1]; Who[i] = Who[i << 1 | 1]; }
    }

    public int Max(int L = 0, int R = int.MaxValue) { int d; return Max(out d, L, R); }
    public int Max(out int index, int L = 0, int R = int.MaxValue)
    {
        index = -1;
        int res = int.MinValue;
        Q[0] = 1L << 32;
        for (int s = 0, t = 1, len = N, first = 1; s != t; ++s)
        {
            int i = (int)(Q[s] >> 32), a = (int)Q[s];
            if (s == first) { len >>= 1; first = t; }
            if (Val[i] < res || Val[i] == res && Who[i] > index) continue;
            if (a >= L && a + len <= R) { res = Val[i]; index = Who[i]; continue; }
            int mid = a + (len >> 1);
            if (L < mid) Q[t++] = ((long)(i << 1) << 32) + a;
            if (R > mid) Q[t++] = ((long)(i << 1 | 1) << 32) + mid;
        }
        return res;
    }

    public int Pop(int L = 0, int R = int.MaxValue)
    {
        int index;
        int maxVal = Max(out index, L, R);
        return PopAt(index);
    }

    public int PopAt(int index)
    {
        int val = heap[index].Pop();
        int i = index + N;
        Val[i] = heap[index].Peek();
        for (i >>= 1; i > 0; i >>= 1)
            if (Val[i << 1] >= Val[i << 1 | 1]) { Val[i] = Val[i << 1]; Who[i] = Who[i << 1]; }
            else { Val[i] = Val[i << 1 | 1]; Who[i] = Who[i << 1 | 1]; }
        return val;
    }
}

public class HeapMax
{
    int[] A;

    public HeapMax(int size = 1000) { A = new int[size]; }
    public int Count { get; private set; }
    public int Peek() { return A[1]; }

    public void Push(int val)
    {
        int i = ++Count;
        if (i == A.Length) Array.Resize(ref A, A.Length * 2);
        for (; i > 1 && val > A[i >> 1]; i >>= 1) A[i] = A[i >> 1];
        A[i] = val;
    }

    public int Pop()
    {
        int res = A[1], val = A[Count--];
        if (Count == 0) return res;
        int i = 1;
        for (int L = i << 1; L <= Count; L = i << 1)
        {
            if (L + 1 <= Count && A[L + 1] > A[L]) L++;
            if (A[L] > val) { A[i] = A[L]; i = L; }
            else break;
        }
        A[i] = val;
        return res;
    }
}




class Entry { static void Main() { new Program().Solve(); } }
class Reader
{
    static TextReader reader = Console.In;
    static readonly char[] separator = { ' ' };
    static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries;
    static string[] A = new string[0];
    static int i;
    static void Init() { Dispose(); A = new string[0]; }
    public static void Set(TextReader r) { Init(); reader = r; }
    public static void Set(string file) { Init(); reader = new StreamReader(file); }
    public static bool HasNext() { return CheckNext(); }
    public static string String() { return Next(); }
    public static int Int() { return int.Parse(Next()); }
    public static long Long() { return long.Parse(Next()); }
    public static double Double() { return double.Parse(Next()); }
    public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); }
    public static int[] IntArray(int N) { return Range(N, Int); }
    public static int[][] IntTable(int H) { return Range(H, IntLine); }
    public static string[] StringArray(int N) { return Range(N, Next); }
    public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); }
    public static string Line() { return reader.ReadLine().Trim(); }
    public static T[] Range<T>(int N, Func<T> f) { var r = new T[N]; for (int i = 0; i < N; r[i++] = f()) ; return r; }
    public static void Dispose() { reader.Dispose(); }
    static string[] Split(string s) { return s.Split(separator, op); }
    static string Next() { CheckNext(); return A[i++]; }
    static bool CheckNext()
    {
        if (i < A.Length) return true;
        string line = reader.ReadLine();
        if (line == null) return false;
        if (line == "") return CheckNext();
        A = Split(line);
        i = 0;
        return true;
    }
}