結果

問題 No.2888 Mamehinata
ユーザー kakeyamay
提出日時 2025-03-27 05:10:08
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 1,838 bytes
コンパイル時間 4,553 ms
コンパイル使用メモリ 88,928 KB
実行使用メモリ 54,456 KB
最終ジャッジ日時 2025-03-27 05:10:22
合計ジャッジ時間 13,372 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 41
権限があれば一括ダウンロードができます

ソースコード

diff #

import java.awt.Color;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.List;
import java.util.Scanner;

public class prog {
  private static enum Color {
    BLACK,
    WHITE,
    RED,
  }

  private static class Vertex {
    public Color color;
    public List<Integer> adjacents;

    Vertex(Color color, List<Integer> adjacents) {
      this.color = color;
      this.adjacents = adjacents;
    }
  }

  public static void main(String[] args) {
    try (Scanner scanner = new Scanner(System.in)) {
      int N = scanner.nextInt();
      int M = scanner.nextInt();

      List<Vertex> graph = new ArrayList<>();
      for (int i = 0; i < N; ++i) {
        graph.add(new Vertex(Color.WHITE, new ArrayList<>()));
      }

      for (int i = 0; i < M; ++i) {
        int u = scanner.nextInt();
        int v = scanner.nextInt();
        --u;
        --v;
        graph.get(u).adjacents.add(v);
        graph.get(v).adjacents.add(u);
      }

      Queue<Integer> blacks = new ArrayDeque<>();
      Queue<Integer> reds = new ArrayDeque<>();

      blacks.add(0);
      graph.get(0).color = Color.BLACK;

      for (int t = 0; t < N; ++t) {
        // step 1
        for (Integer i : blacks) {
          for (Integer j : graph.get(i).adjacents) {
            Vertex vertex = graph.get(j);
            if (vertex.color == Color.WHITE) {
              vertex.color = Color.RED;
              reds.add(j);
            }
          }
        }

        // step 2
        while (!blacks.isEmpty()) {
          graph.get(blacks.poll()).color = Color.WHITE;
        }

        // step 3
        while (!reds.isEmpty()) {
          Integer i = reds.poll();
          graph.get(i).color = Color.BLACK;
          blacks.add(i);
        }

        System.out.println(blacks.size());
      }
    }
  }
}
0