Submission #992921


Source Code Expand

import static java.lang.System.in;
import static java.lang.System.out;

import java.io.*;
import java.util.*;

public class Main {
	static final double EPS = 1e-10;
	static final double INF = 1L << 31;
	static final double PI = Math.PI;

	public static Scanner sc = new Scanner(in);
	StringBuilder sb = new StringBuilder();
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
	public class UnionFind {

		  private int[] _parent;
		  private int[] _rank;


		  public int find(int i) {

		    int p = _parent[i];
		    if (i == p) {
		      return i;
		    }
		    return _parent[i] = find(p);

		  }


		  public void union(int i, int j) {

		    int root1 = find(i);
		    int root2 = find(j);

		    if (root2 == root1) return;

		    if (_rank[root1] > _rank[root2]) {
		      _parent[root2] = root1;
		    } else if (_rank[root2] > _rank[root1]) {
		      _parent[root1] = root2;
		    } else {
		      _parent[root2] = root1;
		      _rank[root1]++;
		    }
		  }


		  public UnionFind(int max) {

		    _parent = new int[max];
		    _rank = new int[max];

		    for (int i = 0; i < max; i++) {
		      _parent[i] = i;
		    }
		  }
	}

	public void run() throws IOException {
		String input;
		String[] inputArray;
		input = br.readLine();
		inputArray = input.split(" ");

		int n = Integer.valueOf(inputArray[0]);
		int m = Integer.valueOf(inputArray[1]);
		ArrayList<ArrayList<Integer>> langs = new ArrayList<ArrayList<Integer>>();
		for (int i=0; i<m; i++)
			langs.add(new ArrayList<Integer>());
		for (int i=0; i<n; i++){
			input = br.readLine();
			inputArray = input.split(" ");
			int k =  Integer.valueOf(inputArray[0]);
			for (int j=1; j<=k; j++){
				int l = Integer.valueOf(inputArray[j])-1;
				langs.get(l).add(i);
			}	
		}
		UnionFind U = new UnionFind(n);
		for (int i=0; i<m; i++){
			for (int j=1; j<langs.get(i).size(); j++)
				U.union(langs.get(i).get(0), langs.get(i).get(j));
		}
		int group = U.find(0);
		for (int i=1; i<n; i++){
			if (U.find(i)!=group){
				sb.append("NO");
				ln(sb);
				return;
			}
		}
		sb.append("YES");
		ln(sb);
	}

	public static void main(String[] args) throws IOException {
		new Main().run();
	}
	public static void ln(Object obj) {
		out.println(obj);
	}
}

Submission Info

Submission Time
Task C - Interpretation
User batchunag
Language Java7 (OpenJDK 1.7.0)
Score 400
Code Size 2359 Byte
Status AC
Exec Time 516 ms
Memory 37696 KB

Judge Result

Set Name sample dataset1 dataset2
Score / Max Score 0 / 0 200 / 200 200 / 200
Status
AC × 2
AC × 12
AC × 25
Set Name Test Cases
sample sample-01.txt, sample-02.txt
dataset1 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt
dataset2 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt
Case Name Status Exec Time Memory
01-01.txt AC 134 ms 9168 KB
01-02.txt AC 146 ms 9556 KB
01-03.txt AC 152 ms 9812 KB
01-04.txt AC 151 ms 9808 KB
01-05.txt AC 148 ms 9808 KB
01-06.txt AC 148 ms 9680 KB
01-07.txt AC 150 ms 9684 KB
01-08.txt AC 146 ms 9684 KB
01-09.txt AC 152 ms 9684 KB
01-10.txt AC 153 ms 9940 KB
02-01.txt AC 437 ms 36084 KB
02-02.txt AC 479 ms 33808 KB
02-03.txt AC 410 ms 34628 KB
02-04.txt AC 482 ms 34680 KB
02-05.txt AC 469 ms 32372 KB
02-06.txt AC 451 ms 35456 KB
02-07.txt AC 441 ms 34876 KB
02-08.txt AC 450 ms 33972 KB
02-09.txt AC 516 ms 36308 KB
02-10.txt AC 454 ms 34328 KB
02-11.txt AC 466 ms 37696 KB
02-12.txt AC 436 ms 33484 KB
02-13.txt AC 438 ms 33608 KB
sample-01.txt AC 126 ms 9044 KB
sample-02.txt AC 128 ms 8916 KB