結果

問題 No.812 Change of Class
コンテスト
ユーザー ks2m
提出日時 2019-04-12 23:53:36
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 1,895 bytes
コンパイル時間 3,294 ms
コンパイル使用メモリ 84,156 KB
実行使用メモリ 118,288 KB
最終ジャッジ日時 2024-06-12 19:59:06
合計ジャッジ時間 13,566 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;

public class Main {
	static TreeMap<Integer, Integer> ansMap = new TreeMap<Integer, Integer>();
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
		for (int i = 0; i < m; i++) {
			int p = sc.nextInt();
			int q = sc.nextInt();
			if (map.containsKey(p)) {
				map.get(p).add(q);
			} else {
				Set<Integer> set = new HashSet<Integer>();
				set.add(q);
				map.put(p, set);
			}
			if (map.containsKey(q)) {
				map.get(q).add(p);
			} else {
				Set<Integer> set = new HashSet<Integer>();
				set.add(p);
				map.put(q, set);
			}
		}

		int q = sc.nextInt();
		int[] a = new int[q];
		for (int i = 0; i < q; i++) {
			a[i] = sc.nextInt();
		}
		sc.close();

		for (int i = 0; i < q; i++) {
			Set<Integer> set = map.get(a[i]);
			if (set == null) {
				System.out.println("0 0");
				continue;
			}

			int cnt = set.size();
			int d = 0;
			Set<Integer> baseSet = new HashSet<Integer>();
			baseSet.addAll(set);
			Set<Integer> oldSet = baseSet;
			while (true) {
				Set<Integer> newSet = new HashSet<Integer>();
				Integer[] arr = oldSet.toArray(new Integer[0]);
				for (int key : arr) {
					Set<Integer> val = map.get(key);
					baseSet.addAll(val);
					baseSet.remove(a[i]);
					newSet.addAll(val);
					newSet.remove(a[i]);
				}
				int cnt2 = baseSet.size();
				if (cnt == cnt2) {
					if (d == 0) {
						System.out.println(cnt + " " + 0);
					} else {
						int d2 = 1;
						while (d >= 2) {
							d /= 2;
							d2++;
						}
						System.out.println(cnt + " " + d2);
					}
					break;
				}
				oldSet = newSet;
				cnt = cnt2;
				d++;
			}
		}
	}
}
0