結果

問題 No.416 旅行会社
ユーザー mban
提出日時 2017-03-21 03:05:03
言語 C#
(mono 4.6.2)
結果
TLE  
実行時間 -
コード長 3086 Byte
コンパイル時間 313 ms
使用メモリ 19524 KB

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
in1.txt AC 33 ms
17444 KB
in2.txt AC 31 ms
17444 KB
in3.txt AC 32 ms
15396 KB
in4.txt AC 32 ms
17464 KB
in5.txt AC 31 ms
15436 KB
in6.txt AC 32 ms
15460 KB
in7.txt AC 35 ms
15468 KB
in8.txt AC 46 ms
17784 KB
in9.txt AC 104 ms
19524 KB
line1.txt TLE -
line2.txt -- -
line11.txt -- -
line21.txt -- -
line31.txt -- -
line32.txt -- -
line33.txt -- -
line34.txt -- -
line35.txt -- -
line41.txt -- -
line42.txt -- -
テストケース一括ダウンロード

ソースコード

diff #
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Text;
using System.Text.RegularExpressions;
using System.Linq;
using System.IO;
using System.ComponentModel;


public class Magatro
{
    private static int N, M, Q;
    private static Bridge[] AB, CD;
    private static int[] Anser;
    private static int[] Par;
    private static List<int>[] Group;
    private static int[] Rank;

    private static void Scan()
    {
        string[] s = Console.ReadLine().Split(' ');
        N = int.Parse(s[0]);
        M = int.Parse(s[1]);
        Q = int.Parse(s[2]);
        CD = new Bridge[Q];
        AB = new Bridge[M];
        for (int i = 0; i < M; i++)
        {
            s = Console.ReadLine().Split(' ');
            AB[i] = new Bridge(int.Parse(s[0]) - 1, int.Parse(s[1]) - 1);
        }
        for (int i = 0; i < Q; i++)
        {
            s = Console.ReadLine().Split(' ');
            CD[i] = new Bridge(int.Parse(s[0]) - 1, int.Parse(s[1]) - 1);
        }
    }

    private static bool Same(int x, int y)
    {
        return Root(x) == Root(y);
    }

    private static void Union(int x, int y, int i)
    {
        int rX = Root(x);
        int rY = Root(y);
        if (rX == rY)
        {
            return;
        }
        int rZero = Root(0);
        if (rZero == rX)
        {
            foreach (int j in Group[rY])
            {
                Anser[j] = i;
            }
        }
        else if (rZero == rY)
        {
            foreach (int j in Group[rX])
            {
                Anser[j] = i;
            }
        }
        if (Group[rX].Count < Group[rY].Count)
        {
            Swap(ref rX, ref rY);
        }

        Group[rX].AddRange(Group[rY]);
        Group[rY] = Group[rX];
        if (Rank[rX] < Rank[rY])
        {
            Par[rX] = rY;
        }
        else
        {
            Par[rY] = rX;
            if (Rank[rX] == Rank[rY])
            {
                Rank[rX]++;
            }
        }
    }

    private static void Swap(ref int a, ref int b)
    {
        a ^= b;
        b ^= a;
        a ^= b;
    }

    private static int Root(int x)
    {
        return Par[x] == x ? x : Root(Par[x]);
    }

    static void Main()
    {
        Scan();
        AB = AB.Except(CD).ToArray();
        Par = new int[N];
        Rank = new int[N];
        for (int i = 0; i < N; i++)
        {
            Par[i] = i;
        }
        Group = new List<int>[N];
        for (int i = 0; i < N; i++)
        {
            Group[i] = new List<int>();
            Group[i].Add(i);
        }
        Anser = new int[N];
        foreach (var b in AB)
        {
            Union(b.A, b.B, -1);
        }

        for (int i = Q - 1; i >= 0; i--)
        {
            var b = CD[i];
            Union(b.A, b.B, i + 1);
        }

        for (int i = 1; i < N; i++)
        {
            Console.WriteLine(Anser[i]);
        }
    }

}

struct Bridge
{
    public int A, B;
    public Bridge(int a, int b)
    {
        A = a;
        B = b;
    }
}
0