Submission #2513767
Source Code Expand
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.*; public class Main { public static void main(String[] args) { InputReader in = new InputReader(System.in); PrintWriter out = new PrintWriter(System.out); int n = in.nextInt(); graph = buildGraph(in, n, n-1); char[] s = in.nextToken().toCharArray(); color = new int[n]; for (int i = 0; i < n ; i++) { color[i] = s[i] == 'W' ? 0 : 1; } out.println(solve()); out.flush(); } static void cutBlackLeaf() { int n = graph.length; available = new boolean[n]; Arrays.fill(available, true); int[] deg = new int[n]; int[] que = new int[n]; int qh = 0; for (int i = 0; i < n ; i++) { deg[i] = graph[i].length; if (deg[i] == 1) { if (color[i] == 1) { que[qh++] = i; } } } int qt = 0; while (qt < qh) { int now = que[qt++]; available[now] = false; for (int to : graph[now]) { deg[to]--; if (deg[to] == 1 && color[to] == 1 && available[to]) { que[qh++] = to; } } } for (int i = 0; i < n ; i++) { if (available[i]) { int de = 0; int[] cp = graph[i].clone(); for (int to : cp) { if (available[to]) { de++; } } graph[i] = new int[de]; for (int to : cp) { if (available[to]) { graph[i][--de] = to; } } } else { graph[i] = null; } } } static int solve() { int n = graph.length; if (n == 1) { return color[0]^1; } available = new boolean[n]; cutBlackLeaf(); int root = -1; int vc = 0; for (int i = 0; i < n ; i++) { if (available[i]) { vc++; if (graph[i].length >= 2) { root = i; } } } if (vc <= 1) { // W or nothing return vc; } if (root == -1) { // W-W return 2; } int total = 0; for (int i = 0; i < n ; i++) { if (available[i]) { int gd = graph[i].length; color[i] ^= gd % 2; total += color[i] ^ 1; } } return (vc - 1) * 2 + total - find(root) * 2; } static int find(int rt) { int[] x = dfs0(rt, -1); int[] y = dfs0(x[1], -1); return y[0]; } static int[] dfs0(int now, int par) { int[] best = new int[]{-1, -1}; for (int to : graph[now]) { if (to == par || !available[to]) { continue; } int[] t = dfs0(to, now); if (best[0] < t[0]) { best = t.clone(); } } if (best[0] == -1) { return new int[]{0, now}; } best[0] += color[now] ^ 1; return best; } static boolean[] available; static int[] color; static int[][] graph; static int[][] buildGraph(InputReader in, int n, int m) { int[][] edges = new int[m][]; int[][] graph = new int[n][]; int[] deg = new int[n]; for (int i = 0 ; i < m ; i++) { int a = in.nextInt()-1; int b = in.nextInt()-1; deg[a]++; deg[b]++; edges[i] = new int[]{a, b}; } for (int i = 0 ; i < n ; i++) { graph[i] = new int[deg[i]]; } for (int i = 0 ; i < m ; i++) { int a = edges[i][0]; int b = edges[i][1]; graph[a][--deg[a]] = b; graph[b][--deg[b]] = a; } return graph; } public static void debug(Object... o) { System.err.println(Arrays.deepToString(o)); } public static class InputReader { private static final int BUFFER_LENGTH = 1 << 12; private InputStream stream; private byte[] buf = new byte[BUFFER_LENGTH]; private int curChar; private int numChars; public InputReader(InputStream stream) { this.stream = stream; } private int next() { if (numChars == -1) { throw new InputMismatchException(); } if (curChar >= numChars) { curChar = 0; try { numChars = stream.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (numChars <= 0) return -1; } return buf[curChar++]; } public char nextChar() { return (char) skipWhileSpace(); } public String nextToken() { int c = skipWhileSpace(); StringBuilder res = new StringBuilder(); do { res.append((char) c); c = next(); } while (!isSpaceChar(c)); return res.toString(); } public int nextInt() { return (int) nextLong(); } public long nextLong() { int c = skipWhileSpace(); long sgn = 1; if (c == '-') { sgn = -1; c = next(); } long res = 0; do { if (c < '0' || c > '9') { throw new InputMismatchException(); } res *= 10; res += c - '0'; c = next(); } while (!isSpaceChar(c)); return res * sgn; } public double nextDouble() { return Double.valueOf(nextToken()); } int skipWhileSpace() { int c = next(); while (isSpaceChar(c)) { c = next(); } return c; } boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } } }
Submission Info
Submission Time | |
---|---|
Task | F - Monochrome Cat |
User | hamadu |
Language | Java8 (OpenJDK 1.8.0) |
Score | 800 |
Code Size | 6774 Byte |
Status | AC |
Exec Time | 231 ms |
Memory | 53544 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 800 / 800 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt |
All | 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt, 1_042.txt, 1_043.txt, 1_044.txt, 1_045.txt, 1_046.txt, 1_047.txt, 1_048.txt, 1_049.txt, 1_050.txt, 1_051.txt, 1_052.txt, 1_053.txt, 1_054.txt, 1_055.txt, 1_056.txt, 1_057.txt, 1_058.txt, 1_059.txt, 1_060.txt, 1_061.txt, 1_062.txt, 1_063.txt, 1_064.txt, 1_065.txt, 1_066.txt, 1_067.txt, 1_068.txt, 1_069.txt, 1_070.txt, 1_071.txt, 1_072.txt, 1_073.txt, 1_074.txt, 1_075.txt, 1_076.txt, 1_077.txt, 1_078.txt, 1_079.txt, 1_080.txt, 1_081.txt, 1_082.txt, 1_083.txt, 1_084.txt, 1_085.txt, 1_086.txt, 1_087.txt, 1_088.txt, 1_089.txt, 1_090.txt, 1_091.txt, 1_092.txt, 1_093.txt, 1_094.txt, 1_095.txt, 1_096.txt, 1_097.txt, 1_098.txt, 1_099.txt, 1_100.txt, 1_101.txt, 1_102.txt, 1_103.txt, 1_104.txt, 1_105.txt, 1_106.txt, 1_107.txt, 1_108.txt, 1_109.txt, 1_110.txt, 1_111.txt, 1_112.txt, 1_113.txt, 1_114.txt, 1_115.txt, 1_116.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_000.txt | AC | 69 ms | 19156 KB |
0_001.txt | AC | 68 ms | 18900 KB |
0_002.txt | AC | 69 ms | 19156 KB |
0_003.txt | AC | 70 ms | 19028 KB |
1_003.txt | AC | 68 ms | 21204 KB |
1_004.txt | AC | 68 ms | 19156 KB |
1_005.txt | AC | 69 ms | 21204 KB |
1_006.txt | AC | 69 ms | 18900 KB |
1_007.txt | AC | 69 ms | 19924 KB |
1_008.txt | AC | 69 ms | 18260 KB |
1_009.txt | AC | 69 ms | 18132 KB |
1_010.txt | AC | 68 ms | 19156 KB |
1_011.txt | AC | 68 ms | 18260 KB |
1_012.txt | AC | 68 ms | 18260 KB |
1_013.txt | AC | 69 ms | 18772 KB |
1_014.txt | AC | 67 ms | 17492 KB |
1_015.txt | AC | 69 ms | 18260 KB |
1_016.txt | AC | 70 ms | 19284 KB |
1_017.txt | AC | 71 ms | 18772 KB |
1_018.txt | AC | 67 ms | 17620 KB |
1_019.txt | AC | 67 ms | 19284 KB |
1_020.txt | AC | 69 ms | 20564 KB |
1_021.txt | AC | 67 ms | 17620 KB |
1_022.txt | AC | 69 ms | 18900 KB |
1_023.txt | AC | 69 ms | 18388 KB |
1_024.txt | AC | 68 ms | 21204 KB |
1_025.txt | AC | 68 ms | 17364 KB |
1_026.txt | AC | 69 ms | 18260 KB |
1_027.txt | AC | 71 ms | 18772 KB |
1_028.txt | AC | 71 ms | 18772 KB |
1_029.txt | AC | 67 ms | 19540 KB |
1_030.txt | AC | 69 ms | 17876 KB |
1_031.txt | AC | 68 ms | 19796 KB |
1_032.txt | AC | 69 ms | 19412 KB |
1_033.txt | AC | 68 ms | 20564 KB |
1_034.txt | AC | 69 ms | 21076 KB |
1_035.txt | AC | 68 ms | 19284 KB |
1_036.txt | AC | 70 ms | 21076 KB |
1_037.txt | AC | 69 ms | 19024 KB |
1_038.txt | AC | 71 ms | 18260 KB |
1_039.txt | AC | 71 ms | 19156 KB |
1_040.txt | AC | 70 ms | 19156 KB |
1_041.txt | AC | 69 ms | 18900 KB |
1_042.txt | AC | 70 ms | 18772 KB |
1_043.txt | AC | 69 ms | 21076 KB |
1_044.txt | AC | 68 ms | 19156 KB |
1_045.txt | AC | 143 ms | 33088 KB |
1_046.txt | AC | 150 ms | 36408 KB |
1_047.txt | AC | 146 ms | 28372 KB |
1_048.txt | AC | 141 ms | 25940 KB |
1_049.txt | AC | 204 ms | 45208 KB |
1_050.txt | AC | 185 ms | 41376 KB |
1_051.txt | AC | 177 ms | 42952 KB |
1_052.txt | AC | 102 ms | 20948 KB |
1_053.txt | AC | 137 ms | 25812 KB |
1_054.txt | AC | 117 ms | 21460 KB |
1_055.txt | AC | 176 ms | 40704 KB |
1_056.txt | AC | 125 ms | 24404 KB |
1_057.txt | AC | 77 ms | 20692 KB |
1_058.txt | AC | 158 ms | 34388 KB |
1_059.txt | AC | 119 ms | 21844 KB |
1_060.txt | AC | 141 ms | 25812 KB |
1_061.txt | AC | 192 ms | 45300 KB |
1_062.txt | AC | 152 ms | 32056 KB |
1_063.txt | AC | 162 ms | 38596 KB |
1_064.txt | AC | 141 ms | 29524 KB |
1_065.txt | AC | 84 ms | 19156 KB |
1_066.txt | AC | 139 ms | 27348 KB |
1_067.txt | AC | 113 ms | 25556 KB |
1_068.txt | AC | 141 ms | 26580 KB |
1_069.txt | AC | 123 ms | 26156 KB |
1_070.txt | AC | 144 ms | 30036 KB |
1_071.txt | AC | 141 ms | 27988 KB |
1_072.txt | AC | 126 ms | 24148 KB |
1_073.txt | AC | 107 ms | 21076 KB |
1_074.txt | AC | 83 ms | 19540 KB |
1_075.txt | AC | 154 ms | 29136 KB |
1_076.txt | AC | 199 ms | 39516 KB |
1_077.txt | AC | 140 ms | 27348 KB |
1_078.txt | AC | 114 ms | 21332 KB |
1_079.txt | AC | 141 ms | 32192 KB |
1_080.txt | AC | 150 ms | 28364 KB |
1_081.txt | AC | 210 ms | 49120 KB |
1_082.txt | AC | 214 ms | 47380 KB |
1_083.txt | AC | 149 ms | 27476 KB |
1_084.txt | AC | 148 ms | 30036 KB |
1_085.txt | AC | 200 ms | 49952 KB |
1_086.txt | AC | 231 ms | 53544 KB |
1_087.txt | AC | 197 ms | 38568 KB |
1_088.txt | AC | 179 ms | 39212 KB |
1_089.txt | AC | 136 ms | 27860 KB |
1_090.txt | AC | 132 ms | 27220 KB |
1_091.txt | AC | 194 ms | 40756 KB |
1_092.txt | AC | 133 ms | 30548 KB |
1_093.txt | AC | 201 ms | 45080 KB |
1_094.txt | AC | 224 ms | 46300 KB |
1_095.txt | AC | 149 ms | 28500 KB |
1_096.txt | AC | 149 ms | 27988 KB |
1_097.txt | AC | 207 ms | 43024 KB |
1_098.txt | AC | 197 ms | 46636 KB |
1_099.txt | AC | 193 ms | 39708 KB |
1_100.txt | AC | 198 ms | 40144 KB |
1_101.txt | AC | 134 ms | 28884 KB |
1_102.txt | AC | 145 ms | 28500 KB |
1_103.txt | AC | 189 ms | 39088 KB |
1_104.txt | AC | 174 ms | 36940 KB |
1_105.txt | AC | 194 ms | 42864 KB |
1_106.txt | AC | 189 ms | 39892 KB |
1_107.txt | AC | 149 ms | 28244 KB |
1_108.txt | AC | 148 ms | 26836 KB |
1_109.txt | AC | 194 ms | 40712 KB |
1_110.txt | AC | 185 ms | 40464 KB |
1_111.txt | AC | 191 ms | 37532 KB |
1_112.txt | AC | 198 ms | 40648 KB |
1_113.txt | AC | 147 ms | 28596 KB |
1_114.txt | AC | 146 ms | 27348 KB |
1_115.txt | AC | 189 ms | 40872 KB |
1_116.txt | AC | 182 ms | 39240 KB |