Submission #57526


Source Code Expand

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);
	static int N, M;
	static long E;
	static StringBuilder out = new StringBuilder();
	static boolean[][] g;

	public static void main(String[] args) {
		N = sc.nextInt();
		M = sc.nextInt();
		E = ((long) N) * (N - 1) / 2;
		if (E - M > N - 1) {
			for (int i = 0; i < M; ++i) {
				out.append("no\n");
			}
			System.out.print(out);
			return;
		}
		g = new boolean[N][N];
		for (boolean[] a : g) {
			Arrays.fill(a, true);
		}
		for (int i = 0; i < N; ++i) {
			g[i][i] = false;
		}
		for (int i = 0; i < M; ++i) {
			int S = Integer.parseInt(sc.next()) - 1;
			int T = Integer.parseInt(sc.next()) - 1;
			g[S][T] = g[T][S] = !g[S][T];
			if (g[S][T]) {
				++E;
			} else {
				--E;
			}
			out.append(calc() ? "yes\n" : "no\n");
		}
		System.out.print(out);
	}

	static boolean calc() {
		if (E > N - 1) return false;
		if (E <= 2) return true;
		boolean[] used = new boolean[N];
		for (int i = 0; i < N; ++i) {
			if (used[i]) continue;
			used[i] = true;
			if (!dfs(i, -1, used)) {
				return false;
			}
		}
		return true;
	}

	static boolean dfs(int pos, int from, boolean[] used) {
		for (int i = 0; i < N; ++i) {
			if (!g[pos][i] || i == from) continue;
			if (used[i]) return false;
			used[i] = true;
			dfs(i, pos, used);
		}
		return true;
	}

}

Submission Info

Submission Time
Task C - 森ですか?
User tomerun
Language Java (OpenJDK 1.7.0)
Score 0
Code Size 1446 Byte
Status WA
Exec Time 2038 ms
Memory 46692 KB

Judge Result

Set Name Easy All
Score / Max Score 0 / 50 0 / 50
Status
AC × 34
WA × 3
AC × 56
WA × 15
TLE × 8
Set Name Test Cases
Easy easy_01_00.txt, easy_01_01.txt, easy_01_02.txt, easy_01_03.txt, easy_01_04.txt, easy_02_00.txt, easy_02_01.txt, easy_02_02.txt, easy_02_03.txt, easy_02_04.txt, easy_03_00.txt, easy_03_01.txt, easy_03_02.txt, easy_03_03.txt, easy_03_04.txt, easy_04_00.txt, easy_04_01.txt, easy_04_02.txt, easy_04_03.txt, easy_04_04.txt, easy_05_00.txt, easy_05_01.txt, easy_05_02.txt, easy_05_03.txt, easy_05_04.txt, easy_06_00.txt, easy_06_01.txt, easy_06_02.txt, easy_06_03.txt, easy_06_04.txt, easy_07_00.txt, easy_07_01.txt, easy_07_02.txt, easy_07_03.txt, easy_07_04.txt, easy_08_00.txt, easy_08_01.txt
All easy_01_00.txt, easy_01_01.txt, easy_01_02.txt, easy_01_03.txt, easy_01_04.txt, easy_02_00.txt, easy_02_01.txt, easy_02_02.txt, easy_02_03.txt, easy_02_04.txt, easy_03_00.txt, easy_03_01.txt, easy_03_02.txt, easy_03_03.txt, easy_03_04.txt, easy_04_00.txt, easy_04_01.txt, easy_04_02.txt, easy_04_03.txt, easy_04_04.txt, easy_05_00.txt, easy_05_01.txt, easy_05_02.txt, easy_05_03.txt, easy_05_04.txt, easy_06_00.txt, easy_06_01.txt, easy_06_02.txt, easy_06_03.txt, easy_06_04.txt, easy_07_00.txt, easy_07_01.txt, easy_07_02.txt, easy_07_03.txt, easy_07_04.txt, easy_08_00.txt, easy_08_01.txt, hard_01_00.txt, hard_01_01.txt, hard_01_02.txt, hard_01_03.txt, hard_01_04.txt, hard_02_00.txt, hard_02_01.txt, hard_02_02.txt, hard_02_03.txt, hard_02_04.txt, hard_03_00.txt, hard_03_01.txt, hard_03_02.txt, hard_03_03.txt, hard_03_04.txt, hard_04_00.txt, hard_04_01.txt, hard_04_02.txt, hard_04_03.txt, hard_04_04.txt, hard_05_00.txt, hard_05_01.txt, hard_05_02.txt, hard_05_03.txt, hard_05_04.txt, hard_06_00.txt, hard_06_01.txt, hard_06_02.txt, hard_06_03.txt, hard_06_04.txt, hard_07_00.txt, hard_07_01.txt, hard_07_02.txt, hard_07_03.txt, hard_07_04.txt, hard_08_00.txt, hard_08_01.txt, hard_09_00.txt, hard_09_01.txt, hard_09_02.txt, hard_09_03.txt, hard_09_04.txt
Case Name Status Exec Time Memory
easy_01_00.txt AC 536 ms 21048 KB
easy_01_01.txt AC 458 ms 20588 KB
easy_01_02.txt WA 464 ms 20648 KB
easy_01_03.txt AC 451 ms 20596 KB
easy_01_04.txt AC 730 ms 20652 KB
easy_02_00.txt AC 439 ms 20272 KB
easy_02_01.txt AC 438 ms 20200 KB
easy_02_02.txt AC 444 ms 20284 KB
easy_02_03.txt AC 446 ms 20132 KB
easy_02_04.txt AC 446 ms 20256 KB
easy_03_00.txt AC 457 ms 20576 KB
easy_03_01.txt AC 450 ms 20832 KB
easy_03_02.txt WA 458 ms 20652 KB
easy_03_03.txt AC 458 ms 20656 KB
easy_03_04.txt AC 465 ms 20708 KB
easy_04_00.txt AC 452 ms 20280 KB
easy_04_01.txt AC 449 ms 20296 KB
easy_04_02.txt AC 446 ms 20200 KB
easy_04_03.txt AC 448 ms 20196 KB
easy_04_04.txt AC 437 ms 20272 KB
easy_05_00.txt AC 458 ms 20660 KB
easy_05_01.txt AC 455 ms 20692 KB
easy_05_02.txt AC 464 ms 20584 KB
easy_05_03.txt AC 472 ms 20892 KB
easy_05_04.txt AC 457 ms 20652 KB
easy_06_00.txt AC 439 ms 20176 KB
easy_06_01.txt AC 437 ms 20184 KB
easy_06_02.txt AC 450 ms 20144 KB
easy_06_03.txt AC 442 ms 20204 KB
easy_06_04.txt AC 444 ms 20148 KB
easy_07_00.txt AC 506 ms 20648 KB
easy_07_01.txt AC 492 ms 20708 KB
easy_07_02.txt AC 476 ms 20712 KB
easy_07_03.txt AC 474 ms 20552 KB
easy_07_04.txt WA 465 ms 20632 KB
easy_08_00.txt AC 469 ms 20656 KB
easy_08_01.txt AC 467 ms 20708 KB
hard_01_00.txt AC 895 ms 42748 KB
hard_01_01.txt AC 926 ms 45976 KB
hard_01_02.txt AC 920 ms 45688 KB
hard_01_03.txt AC 918 ms 45460 KB
hard_01_04.txt AC 936 ms 45764 KB
hard_02_00.txt AC 491 ms 22712 KB
hard_02_01.txt AC 487 ms 24092 KB
hard_02_02.txt AC 486 ms 24656 KB
hard_02_03.txt AC 489 ms 25564 KB
hard_02_04.txt AC 498 ms 24116 KB
hard_03_00.txt WA 1195 ms 45824 KB
hard_03_01.txt WA 945 ms 46116 KB
hard_03_02.txt WA 1332 ms 45680 KB
hard_03_03.txt WA 1182 ms 45716 KB
hard_03_04.txt WA 1409 ms 45948 KB
hard_04_00.txt WA 1060 ms 46068 KB
hard_04_01.txt AC 477 ms 24268 KB
hard_04_02.txt AC 821 ms 44444 KB
hard_04_03.txt AC 474 ms 23144 KB
hard_04_04.txt AC 806 ms 43232 KB
hard_05_00.txt AC 1801 ms 45516 KB
hard_05_01.txt TLE 2037 ms 44684 KB
hard_05_02.txt TLE 2038 ms 45828 KB
hard_05_03.txt TLE 2038 ms 45780 KB
hard_05_04.txt AC 1799 ms 45500 KB
hard_06_00.txt AC 474 ms 22604 KB
hard_06_01.txt AC 480 ms 22316 KB
hard_06_02.txt AC 486 ms 24108 KB
hard_06_03.txt AC 1488 ms 44276 KB
hard_06_04.txt TLE 2037 ms 44332 KB
hard_07_00.txt WA 1960 ms 42212 KB
hard_07_01.txt TLE 2037 ms 45048 KB
hard_07_02.txt TLE 2038 ms 44764 KB
hard_07_03.txt TLE 2037 ms 45280 KB
hard_07_04.txt TLE 2037 ms 45220 KB
hard_08_00.txt AC 1102 ms 45260 KB
hard_08_01.txt AC 460 ms 25120 KB
hard_09_00.txt WA 980 ms 43632 KB
hard_09_01.txt WA 936 ms 46544 KB
hard_09_02.txt WA 920 ms 46692 KB
hard_09_03.txt WA 964 ms 46412 KB
hard_09_04.txt WA 938 ms 46688 KB
sample1.txt AC 418 ms 19900 KB
sample2.txt AC 424 ms 19856 KB