結果
問題 | No.3056 Disconnected Coloring |
ユーザー |
![]() |
提出日時 | 2025-03-14 22:00:32 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 974 ms / 2,000 ms |
コード長 | 2,534 bytes |
コンパイル時間 | 2,931 ms |
コンパイル使用メモリ | 81,476 KB |
実行使用メモリ | 90,620 KB |
最終ジャッジ日時 | 2025-03-14 22:01:04 |
合計ジャッジ時間 | 25,109 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 34 |
ソースコード
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.List; import java.util.Queue; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] sa = br.readLine().split(" "); int n = Integer.parseInt(sa[0]); int m = Integer.parseInt(sa[1]); int[] u = new int[m]; int[] v = new int[m]; Hen[] arr = new Hen[m]; List<List<Hen>> list = new ArrayList<>(n); for (int i = 0; i < n; i++) { list.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { sa = br.readLine().split(" "); u[i] = Integer.parseInt(sa[0]) - 1; v[i] = Integer.parseInt(sa[1]) - 1; Hen h = new Hen(); h.u = u[i]; h.v = v[i]; arr[i] = h; list.get(h.u).add(h); list.get(h.v).add(h); } br.close(); if (m % 2 == 1) { System.out.println(-1); return; } int m2 = m / 2; if (list.get(0).size() > m2 || list.get(n - 1).size() > m2) { int b = 0; if (list.get(0).size() > m2) { b = bfs(list, n - 1, 0); } else { b = bfs(list, 0, n - 1); } for (Hen h : arr) { if (!h.ng) { if (b < m2) { h.c = 'B'; b++; } else { h.c = 'R'; } } } StringBuilder sb = new StringBuilder(); for (Hen h : arr) { if (h.c == '\u0000') { if (b < m2) { h.c = 'B'; b++; } else { h.c = 'R'; } } sb.append(h.c); } System.out.println(sb.toString()); return; } for (int i = 0; i < m; i++) { if (u[i] == 0 && v[i] == n - 1) { System.out.println(-1); return; } } char[] s = new char[m]; int b = 0; for (int i = 0; i < m; i++) { if (u[i] == 0) { s[i] = 'B'; b++; } if (v[i] == n - 1) { s[i] = 'R'; } } for (int i = 0; i < m; i++) { if (s[i] == '\u0000') { if (b < m2) { s[i] = 'B'; b++; } else { s[i] = 'R'; } } } System.out.println(s); } static int bfs(List<List<Hen>> list, int s, int t) { Queue<Integer> que = new ArrayDeque<>(); que.add(s); int b = 0; while (!que.isEmpty()) { int cur = que.poll(); for (Hen h : list.get(cur)) { if (h.c == '\u0000') { int next = h.u; if (next == cur) { next = h.v; } h.ng = true; if (next != t) { h.c = 'B'; b++; que.add(next); } } } } return b; } static class Hen { int u, v; char c; boolean ng; } }