結果

問題 No.416 旅行会社
コンテスト
ユーザー mban
提出日時 2017-03-21 03:05:03
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 3,086 bytes
コンパイル時間 1,090 ms
コンパイル使用メモリ 107,904 KB
実行使用メモリ 35,200 KB
最終ジャッジ日時 2024-07-05 04:51:17
合計ジャッジ時間 11,905 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

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