oj.uz

Submission #733496

# Submission time Handle Problem Language Result Execution time Memory
733496 2023-05-01T00:29:22 Z rahulverma Ronald (COCI17_ronald) Java 11
120 / 120
 814 ms 24148 KB 
import java.io.*;
import java.util.*;

class ronald{
	public static int n;
	public static int m;
	public static int[][] graph;
	public static int[] seen;
	public static ArrayList<ArrayList<Integer>> ccs = new ArrayList<>();
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		n = s.nextInt();
		m = s.nextInt();
		graph = new int[n][n];
		seen = new int[n];
		for(int i = 0; i < m; i++) {
			int v1 = s.nextInt() - 1;
			int v2 = s.nextInt() - 1;
			graph[v1][v2] = 1;
			graph[v2][v1] = 1;
		}
		int c = 0;
		for(int i = 0; i < n; i++) {
			if(seen[i] == 0) {
				ccs.add(new ArrayList<Integer>());
				dfs(i, c);
				c++;
			}
		}
		if(c > 2) {
			System.out.println("NE");
			return;
		}
		boolean works = true;
		for(int i = 0; i < c; i++) {
			boolean w = true;
			for(int node: ccs.get(i)) {
				for(int node2: ccs.get(i)) {
					if(node == node2) continue;
					if(graph[node][node2] == 0) {
						w = false;
						break;
					}
				}
				if(!w) {
					works = false;
					break;
				}
			}
			if(!works) break;
		}
		if(works) System.out.println("DA");
		else System.out.println("NE");
	}
	public static void dfs(int node, int c) {
		seen[node] = 1;
		ccs.get(c).add(node);
		for(int node2 = 0; node2 < n; node2++) {
			if(graph[node][node2] == 1 && seen[node2] == 0) {
				dfs(node2, c);
			}
		}
	}

}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 10388 KB Output is correct
2 Correct 97 ms 10008 KB Output is correct
3 Correct 101 ms 10388 KB Output is correct
4 Correct 96 ms 10216 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 10248 KB Output is correct
2 Correct 95 ms 10372 KB Output is correct
3 Correct 103 ms 10276 KB Output is correct
4 Correct 97 ms 10072 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 10084 KB Output is correct
2 Correct 117 ms 10336 KB Output is correct
3 Correct 100 ms 10576 KB Output is correct
4 Correct 111 ms 10588 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 10180 KB Output is correct
2 Correct 126 ms 10972 KB Output is correct
3 Correct 119 ms 10936 KB Output is correct
4 Correct 113 ms 10928 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 10892 KB Output is correct
2 Correct 94 ms 10128 KB Output is correct
3 Correct 193 ms 12764 KB Output is correct
4 Correct 151 ms 11640 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 12828 KB Output is correct
2 Correct 254 ms 13464 KB Output is correct
3 Correct 323 ms 15428 KB Output is correct
4 Correct 263 ms 13528 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 18356 KB Output is correct
2 Correct 581 ms 20108 KB Output is correct
3 Correct 550 ms 18528 KB Output is correct
4 Correct 486 ms 18708 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 18180 KB Output is correct
2 Correct 517 ms 19532 KB Output is correct
3 Correct 675 ms 23352 KB Output is correct
4 Correct 814 ms 24148 KB Output is correct