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 |
|
|
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 |