Submission #2502267
Source Code Expand
import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; public class Main { static InputStream is; static PrintWriter out; static String INPUT = ""; static void solve() { int n = ni(); int[] from = new int[n - 1]; int[] to = new int[n - 1]; for (int i = 0; i < n - 1; i++) { from[i] = ni() - 1; to[i] = ni() - 1; } int[][] g = packU(n, from, to); int[][] pars = parents3(g, 0); int[] par = pars[0], ord = pars[1], dep = pars[2]; char[] s = ns().toCharArray(); int[][] dpr = new int[2][n]; // return flip int[][] dpg = new int[2][n]; // go for(int i = n-1;i >= 0;i--){ int cur = ord[i]; int rsum = 0; int tog = 0; int ming = 0; for(int e : g[cur]){ if(par[cur] == e)continue; if(dpr[0][e] > 0){ rsum += dpr[1][e] + 2; tog++; ming = Math.min(ming, (dpg[1][e] + 1) - (dpr[1][e] + 2) ); } } int[] res = process(rsum, s[cur], tog, ming); dpr[0][cur] = res[0]; dpr[1][cur] = res[1]; dpg[0][cur] = res[2]; dpg[1][cur] = res[3]; } int ans = Integer.MAX_VALUE; int[][] ddpr = new int[2][n]; int[][] ddpg = new int[2][n]; for(int i = 0;i < n;i++){ int cur = ord[i]; // tr(cur); // tr(ddpr[0][cur], ddpr[1][cur]); // tr(ddpg[0][cur], ddpg[1][cur]); int rsum = 0; int tog = 0; int ming1 = 0; int ming2 = 0; for(int e : g[cur]){ if(par[cur] == e)continue; if(dpr[0][e] > 0){ rsum += dpr[1][e] + 2; tog++; int v = (dpg[1][e] + 1) - (dpr[1][e] + 2); if(v < ming1){ ming2 = ming1; ming1 = v; }else if(v < ming2){ ming2 = v; } } } if(ddpr[0][cur] > 0){ rsum += ddpr[1][cur] + 2; tog++; int v = (ddpg[1][cur] + 1) - (ddpr[1][cur] + 2); if(v < ming1){ ming2 = ming1; ming1 = v; }else if(v < ming2){ ming2 = v; } } { int[] res = process(rsum, s[cur], tog, ming1); // tr(cur, res); ans = Math.min(ans, res[2]); } for(int e : g[cur]){ if(par[cur] == e)continue; int lrsum = rsum, ltog = tog; int lming = ming1; if(dpr[0][e] > 0){ lrsum -= (dpr[1][e] + 2); ltog -= 1; int v = (dpg[1][e] + 1) - (dpr[1][e] + 2); lming = ming1 == v ? ming2 : ming1; } // tr(cur, e, lrsum, ltog, lming, s[cur]); int[] res = process(lrsum, s[cur], ltog, lming); ddpr[0][e] = res[0]; ddpr[1][e] = res[1]; ddpg[0][e] = res[2]; ddpg[1][e] = res[3]; } } // tr(dpr); // tr(dpg); out.println(ans); } static int[] process(int rsum, char c, int tog, int ming) { if(rsum == 0){ if(c == 'B'){ return new int[]{0, 1, 0, 1}; }else{ return new int[]{1, 0, 1, 0}; } }else{ int[] ret= new int[4]; { char t = c; if(tog % 2 == 1){ t = t == 'B' ? 'W' : 'B'; } ret[0] = rsum + (t == 'W' ? 1 : 0); ret[1] = rsum + (t == 'W' ? 0 : 1); } { char t = c; if(tog % 2 == 0){ t = t == 'B' ? 'W' : 'B'; } ret[2] = rsum + ming + (t == 'W' ? 1 : 0); ret[3] = rsum + ming + (t == 'W' ? 0 : 1); } return ret; } } public static int[][] parents3(int[][] g, int root) { int n = g.length; int[] par = new int[n]; Arrays.fill(par, -1); int[] depth = new int[n]; depth[0] = 0; int[] q = new int[n]; q[0] = root; for (int p = 0, r = 1; p < r; p++) { int cur = q[p]; for (int nex : g[cur]) { if (par[cur] != nex) { q[r++] = nex; par[nex] = cur; depth[nex] = depth[cur] + 1; } } } return new int[][] { par, q, depth }; } static int[][] packU(int n, int[] from, int[] to) { int[][] g = new int[n][]; int[] p = new int[n]; for (int f : from) p[f]++; for (int t : to) p[t]++; for (int i = 0; i < n; i++) g[i] = new int[p[i]]; for (int i = 0; i < from.length; i++) { g[from[i]][--p[from[i]]] = to[i]; g[to[i]][--p[to[i]]] = from[i]; } return g; } public static void main(String[] args) throws Exception { long S = System.currentTimeMillis(); is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); solve(); out.flush(); long G = System.currentTimeMillis(); tr(G-S+"ms"); } private static boolean eof() { if(lenbuf == -1)return true; int lptr = ptrbuf; while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false; try { is.mark(1000); while(true){ int b = is.read(); if(b == -1){ is.reset(); return true; }else if(!isSpaceChar(b)){ is.reset(); return false; } } } catch (IOException e) { return true; } } private static byte[] inbuf = new byte[1024]; static int lenbuf = 0, ptrbuf = 0; private static int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } // private static boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); } private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private static double nd() { return Double.parseDouble(ns()); } private static char nc() { return (char)skip(); } private static String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private static char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private static char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private static int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private static int ni() { int num = 0, b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); } }
Submission Info
Submission Time | |
---|---|
Task | F - Monochrome Cat |
User | uwi |
Language | Java8 (OpenJDK 1.8.0) |
Score | 800 |
Code Size | 7404 Byte |
Status | AC |
Exec Time | 387 ms |
Memory | 48420 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 | 71 ms | 20436 KB |
0_001.txt | AC | 67 ms | 15700 KB |
0_002.txt | AC | 67 ms | 21332 KB |
0_003.txt | AC | 69 ms | 18772 KB |
1_003.txt | AC | 66 ms | 17492 KB |
1_004.txt | AC | 67 ms | 18900 KB |
1_005.txt | AC | 69 ms | 21204 KB |
1_006.txt | AC | 69 ms | 22996 KB |
1_007.txt | AC | 66 ms | 19284 KB |
1_008.txt | AC | 68 ms | 23124 KB |
1_009.txt | AC | 68 ms | 21076 KB |
1_010.txt | AC | 67 ms | 19156 KB |
1_011.txt | AC | 68 ms | 18260 KB |
1_012.txt | AC | 68 ms | 17620 KB |
1_013.txt | AC | 68 ms | 19028 KB |
1_014.txt | AC | 69 ms | 21076 KB |
1_015.txt | AC | 68 ms | 19028 KB |
1_016.txt | AC | 69 ms | 20308 KB |
1_017.txt | AC | 68 ms | 18132 KB |
1_018.txt | AC | 67 ms | 18900 KB |
1_019.txt | AC | 68 ms | 21204 KB |
1_020.txt | AC | 68 ms | 17364 KB |
1_021.txt | AC | 66 ms | 19284 KB |
1_022.txt | AC | 69 ms | 19924 KB |
1_023.txt | AC | 68 ms | 17620 KB |
1_024.txt | AC | 69 ms | 18004 KB |
1_025.txt | AC | 68 ms | 19156 KB |
1_026.txt | AC | 70 ms | 19284 KB |
1_027.txt | AC | 68 ms | 18644 KB |
1_028.txt | AC | 69 ms | 21204 KB |
1_029.txt | AC | 69 ms | 20436 KB |
1_030.txt | AC | 67 ms | 18388 KB |
1_031.txt | AC | 67 ms | 18516 KB |
1_032.txt | AC | 69 ms | 21076 KB |
1_033.txt | AC | 67 ms | 18388 KB |
1_034.txt | AC | 69 ms | 18772 KB |
1_035.txt | AC | 68 ms | 15828 KB |
1_036.txt | AC | 68 ms | 21204 KB |
1_037.txt | AC | 68 ms | 21204 KB |
1_038.txt | AC | 70 ms | 19028 KB |
1_039.txt | AC | 68 ms | 18900 KB |
1_040.txt | AC | 71 ms | 20820 KB |
1_041.txt | AC | 69 ms | 18132 KB |
1_042.txt | AC | 69 ms | 18516 KB |
1_043.txt | AC | 69 ms | 17876 KB |
1_044.txt | AC | 69 ms | 19028 KB |
1_045.txt | AC | 115 ms | 25940 KB |
1_046.txt | AC | 387 ms | 29012 KB |
1_047.txt | AC | 191 ms | 45360 KB |
1_048.txt | AC | 174 ms | 35904 KB |
1_049.txt | AC | 166 ms | 34700 KB |
1_050.txt | AC | 166 ms | 35468 KB |
1_051.txt | AC | 193 ms | 33668 KB |
1_052.txt | AC | 111 ms | 23764 KB |
1_053.txt | AC | 186 ms | 43560 KB |
1_054.txt | AC | 131 ms | 29012 KB |
1_055.txt | AC | 176 ms | 37156 KB |
1_056.txt | AC | 129 ms | 29156 KB |
1_057.txt | AC | 76 ms | 18260 KB |
1_058.txt | AC | 135 ms | 28116 KB |
1_059.txt | AC | 127 ms | 28628 KB |
1_060.txt | AC | 178 ms | 34092 KB |
1_061.txt | AC | 194 ms | 43052 KB |
1_062.txt | AC | 132 ms | 28348 KB |
1_063.txt | AC | 140 ms | 30228 KB |
1_064.txt | AC | 130 ms | 28628 KB |
1_065.txt | AC | 84 ms | 19668 KB |
1_066.txt | AC | 178 ms | 43212 KB |
1_067.txt | AC | 108 ms | 22996 KB |
1_068.txt | AC | 125 ms | 30520 KB |
1_069.txt | AC | 111 ms | 26964 KB |
1_070.txt | AC | 134 ms | 28468 KB |
1_071.txt | AC | 185 ms | 44884 KB |
1_072.txt | AC | 141 ms | 34556 KB |
1_073.txt | AC | 105 ms | 22612 KB |
1_074.txt | AC | 85 ms | 19924 KB |
1_075.txt | AC | 129 ms | 29712 KB |
1_076.txt | AC | 205 ms | 44592 KB |
1_077.txt | AC | 178 ms | 45136 KB |
1_078.txt | AC | 120 ms | 27144 KB |
1_079.txt | AC | 128 ms | 31672 KB |
1_080.txt | AC | 135 ms | 27604 KB |
1_081.txt | AC | 204 ms | 47160 KB |
1_082.txt | AC | 211 ms | 44816 KB |
1_083.txt | AC | 192 ms | 44028 KB |
1_084.txt | AC | 207 ms | 46152 KB |
1_085.txt | AC | 207 ms | 46868 KB |
1_086.txt | AC | 205 ms | 44096 KB |
1_087.txt | AC | 201 ms | 47020 KB |
1_088.txt | AC | 201 ms | 47004 KB |
1_089.txt | AC | 196 ms | 48420 KB |
1_090.txt | AC | 192 ms | 44892 KB |
1_091.txt | AC | 201 ms | 44708 KB |
1_092.txt | AC | 187 ms | 42796 KB |
1_093.txt | AC | 211 ms | 43604 KB |
1_094.txt | AC | 209 ms | 47160 KB |
1_095.txt | AC | 201 ms | 46352 KB |
1_096.txt | AC | 205 ms | 44088 KB |
1_097.txt | AC | 205 ms | 45708 KB |
1_098.txt | AC | 207 ms | 47072 KB |
1_099.txt | AC | 201 ms | 45032 KB |
1_100.txt | AC | 198 ms | 45368 KB |
1_101.txt | AC | 191 ms | 46116 KB |
1_102.txt | AC | 197 ms | 45208 KB |
1_103.txt | AC | 199 ms | 44508 KB |
1_104.txt | AC | 194 ms | 47104 KB |
1_105.txt | AC | 207 ms | 44872 KB |
1_106.txt | AC | 208 ms | 45104 KB |
1_107.txt | AC | 199 ms | 44688 KB |
1_108.txt | AC | 205 ms | 43420 KB |
1_109.txt | AC | 212 ms | 46248 KB |
1_110.txt | AC | 209 ms | 47152 KB |
1_111.txt | AC | 218 ms | 47176 KB |
1_112.txt | AC | 209 ms | 47832 KB |
1_113.txt | AC | 201 ms | 44240 KB |
1_114.txt | AC | 208 ms | 44700 KB |
1_115.txt | AC | 208 ms | 46016 KB |
1_116.txt | AC | 208 ms | 44248 KB |