結果

問題 No.2780 The Bottle Imp
ユーザー ks2mks2m
提出日時 2024-06-07 22:10:26
言語 Java
(openjdk 23)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 7,047 bytes
コンパイル時間 7,800 ms
コンパイル使用メモリ 84,376 KB
実行使用メモリ 98,884 KB
最終ジャッジ日時 2024-12-27 13:50:06
合計ジャッジ時間 16,937 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 39 WA * 1
権限があれば一括ダウンロードができます

ソースコード

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;
}
}
/**
* n0<br>
* O(n)
*
* @param n
*/
public SCC(int n) {
this.n = n;
edges = new ArrayList<>();
}
/**
* fromto<br>
* O(1)
*
* @param from 0≦fromn
* @param to 0≦ton
*/
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>
*
* mO(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;
/**
* n0<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≦an
* @param b 0≦bn
* @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≦an
* @param b 0≦bn
* @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≦an
* @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≦an
* @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;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0