結果

問題 No.416 旅行会社
ユーザー ei1333333ei1333333
提出日時 2016-08-23 00:48:36
言語 Java21
(openjdk 21)
結果
AC  
実行時間 2,456 ms / 4,000 ms
コード長 2,480 bytes
コンパイル時間 2,428 ms
コンパイル使用メモリ 84,024 KB
実行使用メモリ 135,368 KB
最終ジャッジ日時 2024-05-08 14:52:05
合計ジャッジ時間 32,942 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,900 ms
125,728 KB
testcase_01 AC 128 ms
54,020 KB
testcase_02 AC 130 ms
54,056 KB
testcase_03 AC 137 ms
53,988 KB
testcase_04 AC 141 ms
54,112 KB
testcase_05 AC 150 ms
54,264 KB
testcase_06 AC 178 ms
54,432 KB
testcase_07 AC 232 ms
57,320 KB
testcase_08 AC 299 ms
59,308 KB
testcase_09 AC 565 ms
62,040 KB
testcase_10 AC 1,903 ms
124,696 KB
testcase_11 AC 1,805 ms
126,012 KB
testcase_12 AC 1,768 ms
125,800 KB
testcase_13 AC 1,747 ms
125,932 KB
testcase_14 AC 2,456 ms
135,368 KB
testcase_15 AC 2,412 ms
135,004 KB
testcase_16 AC 2,401 ms
135,208 KB
testcase_17 AC 2,456 ms
135,140 KB
testcase_18 AC 2,389 ms
135,232 KB
testcase_19 AC 2,075 ms
128,596 KB
testcase_20 AC 2,054 ms
128,628 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;

public class Main
{
		Scanner cin;
		int N, M, Q;
		int[] A, B, C, D, ret;
		boolean[] V;
		List< HashMap< Integer, Integer > > edgeIdx;
		UnionFind tree;
		List< Queue < Integer > > que;
		
		public static void main(String[] arg)
		{
				new Main().Solve();
		}

		public void Solve()
		{
				cin = new Scanner(System.in);
				
				N = cin.nextInt();
			   M = cin.nextInt();
			   Q = cin.nextInt();
				
				A = new int[M];
				B = new int[M];
			   C = new int[Q];
			   D = new int[Q];

				ret = new int[N];
				 
				V = new boolean[M];
				
			   edgeIdx = new ArrayList<>();
				for(int i = 0; i < N; i++) {
						edgeIdx.add(new HashMap<>());
				}
				
			   tree = new UnionFind(N);

			   que = new ArrayList<>();
				for(int i = 0; i < N; i++) {
						que.add(new ArrayDeque< Integer >());
						que.get(i).add(i);
				}
				
				for(int i = 0; i < M;i++) {
						A[i] = cin.nextInt() - 1;
						B[i] = cin.nextInt() - 1;
						edgeIdx.get(A[i]).put(B[i], i);
				}
				
				for(int i = 0; i < Q; i++) {
						C[i] = cin.nextInt() - 1;
						D[i] = cin.nextInt() - 1;
						V[edgeIdx.get(C[i]).get(D[i])] = true;
				}

				for(int i = 0; i < M; i++) {
						if(!V[i]) Merge(A[i], B[i]);
				}

				
				int root = tree.find(0);
				while(!que.get(root).isEmpty()) {
						ret[que.get(root).poll()] = -1;
				}
				
				for(int i = Q - 1; i >= 0; i--) {
						Merge(C[i], D[i]);
						root = tree.find(0);
						while(!que.get(root).isEmpty()) {
								ret[que.get(root).poll()] = i + 1;
						}
				}

				for(int i = 1; i < N; i++) {
						System.out.println(ret[i]);
				}
		}

		public void Merge(int p, int q)
		{
			   p = tree.find(p);
				q = tree.find(q);
				if(p != q) {
						if(que.get(p).size() < que.get(q).size()) {
								while(!que.get(p).isEmpty()) {
										que.get(q).add(que.get(p).poll());
								}
								tree.unite(q, p);
						} else {
								while(!que.get(q).isEmpty()) {
										que.get(p).add(que.get(q).poll());
								}
								tree.unite(p, q);
						}
				}
				return;
		}
		

		public class UnionFind
		{
				int[] data;

				UnionFind(int sz)
				{
						data = new int[sz];
						Arrays.fill(data, -1);
				}
				int find(int y)
				{
						if(data[y] < 0) return(y);
						return(data[y] = find(data[y]));
				}
				int unite(int x, int y)
				{
						x = find(x);
						y = find(y);
						if(x != y) {
								data[x] += data[y];
								data[y] = x;
						}
						return(find(x));
				}

		}
}
0