結果

問題 No.2780 The Bottle Imp
ユーザー ks2mks2m
提出日時 2024-06-07 22:10:26
言語 Java21
(openjdk 21)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 7,047 bytes
コンパイル時間 2,520 ms
コンパイル使用メモリ 97,144 KB
実行使用メモリ 99,240 KB
最終ジャッジ日時 2024-06-08 10:30:50
合計ジャッジ時間 14,504 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
36,976 KB
testcase_01 AC 44 ms
37,060 KB
testcase_02 AC 45 ms
36,756 KB
testcase_03 AC 44 ms
37,112 KB
testcase_04 AC 44 ms
36,952 KB
testcase_05 AC 47 ms
37,008 KB
testcase_06 AC 47 ms
37,228 KB
testcase_07 AC 287 ms
55,972 KB
testcase_08 AC 293 ms
55,400 KB
testcase_09 AC 285 ms
55,416 KB
testcase_10 AC 290 ms
55,072 KB
testcase_11 AC 287 ms
55,284 KB
testcase_12 AC 466 ms
67,236 KB
testcase_13 AC 473 ms
67,412 KB
testcase_14 AC 224 ms
49,944 KB
testcase_15 AC 219 ms
49,752 KB
testcase_16 AC 215 ms
49,928 KB
testcase_17 AC 220 ms
49,968 KB
testcase_18 AC 220 ms
49,640 KB
testcase_19 AC 221 ms
50,404 KB
testcase_20 AC 230 ms
48,152 KB
testcase_21 AC 229 ms
48,456 KB
testcase_22 AC 200 ms
46,888 KB
testcase_23 AC 229 ms
50,824 KB
testcase_24 AC 269 ms
54,344 KB
testcase_25 AC 370 ms
61,468 KB
testcase_26 AC 258 ms
53,384 KB
testcase_27 AC 291 ms
53,536 KB
testcase_28 AC 290 ms
52,752 KB
testcase_29 AC 250 ms
56,560 KB
testcase_30 AC 235 ms
54,832 KB
testcase_31 AC 342 ms
55,564 KB
testcase_32 AC 188 ms
45,556 KB
testcase_33 AC 411 ms
77,904 KB
testcase_34 AC 511 ms
99,240 KB
testcase_35 AC 175 ms
46,452 KB
testcase_36 AC 46 ms
36,608 KB
testcase_37 AC 46 ms
37,060 KB
testcase_38 AC 179 ms
46,292 KB
testcase_39 AC 351 ms
64,576 KB
testcase_40 AC 354 ms
64,492 KB
testcase_41 AC 378 ms
64,764 KB
testcase_42 WA -
testcase_43 AC 44 ms
36,628 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
	static List<Set<Integer>> list;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] m = new int[n];
		int[][] a = new int[n][];
		for (int i = 0; i < n; i++) {
			String[] sa = br.readLine().split(" ");
			m[i] = Integer.parseInt(sa[0]);
			a[i] = new int[m[i]];
			for (int j = 0; j < m[i]; j++) {
				a[i][j] = Integer.parseInt(sa[j + 1]) - 1;
			}
		}
		br.close();

		SCC scc = new SCC(n);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m[i]; j++) {
				scc.addEdge(i, a[i][j]);
			}
		}
		int[][] g = scc.scc();

		DSU uf = new DSU(n);
		for (int i = 0; i < g.length; i++) {
			for (int j = 1; j < g[i].length; j++) {
				uf.merge(g[i][0], g[i][j]);
			}
		}

		list = new ArrayList<>(n);
		for (int i = 0; i < n; i++) {
			list.add(new HashSet<>());
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m[i]; j++) {
				if (!uf.same(i, a[i][j])) {
					list.get(uf.leader(i)).add(uf.leader(a[i][j]));
				}
			}
		}

		boolean[] vis = new boolean[n];
		boolean res = dfs(uf.leader(0), vis);
		if (!res) {
			System.out.println("No");
			return;
		}
		for (int i = 0; i < n; i++) {
			if (!vis[uf.leader(i)]) {
				System.out.println("No");
				return;
			}
		}
		System.out.println("Yes");
	}

	static boolean dfs(int x, boolean[] vis) {
		vis[x] = true;
		Set<Integer> nexts = list.get(x);
		if (nexts.size() > 1) {
			return false;
		}
		if (nexts.isEmpty()) {
			return true;
		}
		return dfs(nexts.iterator().next(), vis);
	}
}

class SCC {
	/** gid[i]：頂点iが何番目の強連結成分に属しているか */
	int[] gid;

	private final int n;
	private List<Edge> edges;

	private int nowOrd, groupNum;
	private int[] start, low, ord;
	private Edge[] elist;
	private Deque<Integer> visited;

	private class Edge {
		final int from, to;

		public Edge(int from, int to) {
			this.from = from;
			this.to = to;
		}
	}

	/**
	 * n頂点0辺のグラフを作る。<br>
	 * O(n)
	 * 
	 * @param n 頂点数
	 */
	public SCC(int n) {
		this.n = n;
		edges = new ArrayList<>();
	}

	/**
	 * fromからtoへ有向辺を追加する。<br>
	 * ならしO(1)
	 * 
	 * @param from 有向辺の始点（0≦from＜n）
	 * @param to 有向辺の終点（0≦to＜n）
	 */
	void addEdge(int from, int to) {
		assert 0 <= from && from < n : "from=" + from;
		assert 0 <= to && to < n : "to=" + to;

		edges.add(new Edge(from, to));
	}

	/**
	 * <pre>
	 * 強連結成分分解
	 * 辺の本数をmとして、O(n + m)
	 * 
	 * ・全ての頂点がちょうど1つずつ、内側の配列のどれかに含まれる。
	 * ・内側の配列（1つの強連結成分）内での頂点の順序は未定義。
	 * ・外側の配列はトポロジカルソートされている。
	 * </pre>
	 * 
	 * @return 強連結成分ごとの頂点の配列
	 */
	int[][] scc() {
		start = new int[n + 1];
		for (Edge e : edges) {
			start[e.from + 1]++;
		}
		for (int i = 1; i <= n; i++) {
			start[i] += start[i - 1];
		}
		elist = new Edge[edges.size()];
		int[] counter = Arrays.copyOf(start, n + 1);
		for (Edge e : edges) {
			elist[counter[e.from]++] = e;
		}

		nowOrd = 0;
		groupNum = 0;
		visited = new ArrayDeque<>();
		low = new int[n];
		ord = new int[n];
		gid = new int[n];
		Arrays.fill(ord, -1);

		for (int i = 0; i < n; i++) {
			if (ord[i] == -1) {
				dfs(i);
			}
		}
		for (int i = 0; i < n; i++) {
			gid[i] = groupNum - 1 - gid[i];
		}

		int[] counts = new int[groupNum];
		for (int x : gid) {
			counts[x]++;
		}
		int[][] groups = new int[groupNum][];
		for (int i = 0; i < groupNum; i++) {
			groups[i] = new int[counts[i]];
		}
		for (int i = 0; i < n; i++) {
			int idx = gid[i];
			groups[idx][--counts[idx]] = i;
		}
		return groups;
	}

	private void dfs(int v) {
		low[v] = ord[v] = nowOrd++;
		visited.add(v);
		for (int i = start[v]; i < start[v + 1]; i++) {
			int to = elist[i].to;
			if (ord[to] == -1) {
				dfs(to);
				low[v] = Math.min(low[v], low[to]);
			} else {
				low[v] = Math.min(low[v], ord[to]);
			}
		}
		if (low[v] == ord[v]) {
			while (true) {
				int u = visited.pollLast();
				ord[u] = n;
				gid[u] = groupNum;
				if (u == v) {
					break;
				}
			}
			groupNum++;
		}
	}
}

class DSU {
	private int n;
	private int[] parentOrSize;
	private int num;

	/**
	 * n頂点0辺の無向グラフを作る。<br>
	 * O(n)
	 * 
	 * @param n 頂点数
	 */
	public DSU(int n) {
		this.n = n;
		this.parentOrSize = new int[n];
		Arrays.fill(parentOrSize, -1);
		num = n;
	}

	/**
	 * 辺(a, b)を足す。<br>
	 * ならしO(α(n))
	 * 
	 * @param a 頂点番号（0≦a＜n）
	 * @param b 頂点番号（0≦b＜n）
	 * @return 代表元
	 */
	int merge(int a, int b) {
		assert 0 <= a && a < n : "a=" + a;
		assert 0 <= b && b < n : "b=" + b;

		int x = leader(a);
		int y = leader(b);
		if (x == y) {
			return x;
		}
		if (-parentOrSize[x] < -parentOrSize[y]) {
			int tmp = x;
			x = y;
			y = tmp;
		}
		parentOrSize[x] += parentOrSize[y];
		parentOrSize[y] = x;
		num--;
		return x;
	}

	/**
	 * 頂点a, bが連結かどうか。<br>
	 * ならしO(α(n))
	 * 
	 * @param a 頂点番号（0≦a＜n）
	 * @param b 頂点番号（0≦b＜n）
	 * @return true：連結　false：非連結
	 */
	boolean same(int a, int b) {
		assert 0 <= a && a < n : "a=" + a;
		assert 0 <= b && b < n : "b=" + b;

		return leader(a) == leader(b);
	}

	/**
	 * 頂点aの属する連結成分の代表元を返す。<br>
	 * ならしO(α(n))
	 * 
	 * @param a 頂点番号（0≦a＜n）
	 * @return 代表元
	 */
	int leader(int a) {
		assert 0 <= a && a < n : "a=" + a;

		if (parentOrSize[a] < 0) {
			return a;
		} else {
			return parentOrSize[a] = leader(parentOrSize[a]);
		}
	}

	/**
	 * 頂点aの属する連結成分の要素数を返す。<br>
	 * ならしO(α(n))
	 * 
	 * @param a 頂点番号（0≦a＜n）
	 * @return 要素数
	 */
	int size(int a) {
		assert 0 <= a && a < n : "a=" + a;

		return -parentOrSize[leader(a)];
	}

	/**
	 * 連結成分の数を返す。<br>
	 * O(1)
	 * 
	 * @return 連結成分数
	 */
	int num() {
		return num;
	}

	/**
	 * グラフを連結成分に分けた情報を返す。<br>
	 * O(n)
	 * 
	 * @return 「1つの連結成分の頂点番号のリスト」のリスト
	 */
	List<List<Integer>> groups() {
		int[] leaderBuf = new int[n];
		int[] groupSize = new int[n];
		for (int i = 0; i < n; i++) {
			leaderBuf[i] = leader(i);
			groupSize[leaderBuf[i]]++;
		}
		List<List<Integer>> result = new ArrayList<>(n);
		for (int i = 0; i < n; i++) {
			result.add(new ArrayList<>(groupSize[i]));
		}
		for (int i = 0; i < n; i++) {
			result.get(leaderBuf[i]).add(i);
		}
		result.removeIf(List::isEmpty);
		return result;
	}
}
0