Submission #2502759
Source Code Expand
/+ dub.sdl: name "F" dependency "dunkelheit" version=">=0.9.0" +/ import std.stdio, std.algorithm, std.range, std.conv; // import dkh.foundation, dkh.scanner; int solve(int[][] g, bool[] s) { int n = g.length.to!int; foreach (i; 0..n) { if (g[i].length % 2) s[i] = !s[i]; } debug { foreach (v; g) { writeln(v); } writeln(s); } int base = 0; base += 2*(n-1) + s.count(true).to!int; int ans = 0; int dfs(int p, int b) { int[2] buf = [0, 0]; foreach (d; g[p]) { if (d == b) continue; int ch = dfs(d, p); if (ch > buf[0]) swap(ch, buf[0]); if (ch > buf[1]) swap(ch, buf[1]); } if (s[p]) { if (g[p].length.to!int == 1) { buf[0]++; } else { buf[0] += 2; } } ans = max(ans, buf[0] + buf[1]); return buf[0]; } dfs(0, -1); debug writeln("ANS! ", base, " ", ans); return base - ans; } int main() { Scanner sc = new Scanner(stdin); scope(exit) assert(!sc.hasNext); int n; sc.read(n); int[][] g = new int[][n]; foreach (i; 0..n-1) { int a, b; sc.read(a, b); a--; b--; g[a] ~= b; g[b] ~= a; } string s; sc.read(s); int wc = s.count('W').to!int; if (wc == 0) { writeln(0); return 0; } else if (wc == 1) { writeln(1); return 0; } int[] wsz = new int[n]; bool[] enable = new bool[n]; void dfs(int p, int b) { wsz[p] = 0; int chv = 0; if (s[p] == 'W') { wsz[p] = 1; chv = 2; } foreach (d; g[p]) { if (d == b) continue; dfs(d, p); wsz[p] += wsz[d]; if (wsz[d]) chv++; } if (wsz[p] != wc) { chv++; } enable[p] = (chv >= 2); } dfs(0, -1); int n2 = enable.count(true).to!int; int[] newID = new int[n]; int idc = 0; bool[] s2 = new bool[n2]; foreach (i; 0..n) { if (enable[i]) { newID[i] = idc++; s2[newID[i]] = (s[i] == 'W'); } } int[][] ng = new int[][n2]; foreach (i; 0..n) { if (!enable[i]) continue; foreach (j; g[i]) { if (i > j || !enable[j]) continue; ng[newID[i]] ~= newID[j]; ng[newID[j]] ~= newID[i]; } } writeln(solve(ng, s2)); return 0; } /* IMPORT /home/yosupo/Program/dunkelheit/source/dkh/container/stackpayload.d */ // module dkh.container.stackpayload; struct StackPayload(T, size_t MINCAP = 4) if (MINCAP >= 1) { import core.exception : RangeError; private T* _data; private uint len, cap; @property bool empty() const { return len == 0; } @property size_t length() const { return len; } alias opDollar = length; inout(T)[] data() inout { return (_data) ? _data[0..len] : null; } ref inout(T) opIndex(size_t i) inout { version(assert) if (len <= i) throw new RangeError(); return _data[i]; } ref inout(T) front() inout { return this[0]; } ref inout(T) back() inout { return this[$-1]; } void reserve(size_t newCap) { import core.memory : GC; import core.stdc.string : memcpy; import std.conv : to; if (newCap <= cap) return; void* newData = GC.malloc(newCap * T.sizeof); cap = newCap.to!uint; if (len) memcpy(newData, _data, len * T.sizeof); _data = cast(T*)(newData); } void free() { import core.memory : GC; GC.free(_data); } void clear() { len = 0; } void insertBack(T item) { import std.algorithm : max; if (len == cap) reserve(max(cap * 2, MINCAP)); _data[len++] = item; } alias opOpAssign(string op : "~") = insertBack; void removeBack() { assert(!empty, "StackPayload.removeBack: Stack is empty"); len--; } } /* IMPORT /home/yosupo/Program/dunkelheit/source/dkh/foundation.d */ // module dkh.foundation; static if (__VERSION__ <= 2070) { /* Copied by https://github.com/dlang/phobos/blob/master/std/algorithm/iteration.d Copyright: Andrei Alexandrescu 2008-. License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0). */ template fold(fun...) if (fun.length >= 1) { auto fold(R, S...)(R r, S seed) { import std.algorithm : reduce; static if (S.length < 2) { return reduce!fun(seed, r); } else { import std.typecons : tuple; return reduce!fun(tuple(seed), r); } } } } /* IMPORT /home/yosupo/Program/dunkelheit/source/dkh/scanner.d */ // module dkh.scanner; // import dkh.container.stackpayload; class Scanner { import std.stdio : File; import std.conv : to; import std.range : front, popFront, array, ElementType; import std.array : split; import std.traits : isSomeChar, isStaticArray, isArray; import std.algorithm : map; File f; this(File f) { this.f = f; } char[512] lineBuf; char[] line; private bool succW() { import std.range.primitives : empty, front, popFront; import std.ascii : isWhite; while (!line.empty && line.front.isWhite) { line.popFront; } return !line.empty; } private bool succ() { import std.range.primitives : empty, front, popFront; import std.ascii : isWhite; while (true) { while (!line.empty && line.front.isWhite) { line.popFront; } if (!line.empty) break; line = lineBuf[]; f.readln(line); if (!line.length) return false; } return true; } private bool readSingle(T)(ref T x) { import std.algorithm : findSplitBefore; import std.string : strip; import std.conv : parse; if (!succ()) return false; static if (isArray!T) { alias E = ElementType!T; static if (isSomeChar!E) { auto r = line.findSplitBefore(" "); x = r[0].strip.dup; line = r[1]; } else static if (isStaticArray!T) { foreach (i; 0..T.length) { bool f = succW(); assert(f); x[i] = line.parse!E; } } else { StackPayload!E buf; while (succW()) { buf ~= line.parse!E; } x = buf.data; } } else { x = line.parse!T; } return true; } int unsafeRead(T, Args...)(ref T x, auto ref Args args) { if (!readSingle(x)) return 0; static if (args.length == 0) { return 1; } else { return 1 + read(args); } } void read(Args...)(auto ref Args args) { import std.exception; static if (args.length != 0) { enforce(readSingle(args[0])); read(args[1..$]); } } bool hasNext() { return succ(); } } /* This source code generated by dunkelheit and include dunkelheit's source code. dunkelheit's Copyright: Copyright (c) 2016- Kohei Morita. (https://github.com/yosupo06/dunkelheit) dunkelheit's License: MIT License(https://github.com/yosupo06/dunkelheit/blob/master/LICENSE.txt) */
Submission Info
Submission Time | |
---|---|
Task | F - Monochrome Cat |
User | yosupo |
Language | D (LDC 0.17.0) |
Score | 800 |
Code Size | 7995 Byte |
Status | AC |
Exec Time | 87 ms |
Memory | 18200 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 | 1 ms | 256 KB |
0_001.txt | AC | 1 ms | 256 KB |
0_002.txt | AC | 1 ms | 256 KB |
0_003.txt | AC | 1 ms | 256 KB |
1_003.txt | AC | 1 ms | 256 KB |
1_004.txt | AC | 1 ms | 256 KB |
1_005.txt | AC | 1 ms | 256 KB |
1_006.txt | AC | 1 ms | 256 KB |
1_007.txt | AC | 1 ms | 256 KB |
1_008.txt | AC | 1 ms | 256 KB |
1_009.txt | AC | 1 ms | 256 KB |
1_010.txt | AC | 1 ms | 256 KB |
1_011.txt | AC | 1 ms | 256 KB |
1_012.txt | AC | 1 ms | 256 KB |
1_013.txt | AC | 1 ms | 256 KB |
1_014.txt | AC | 1 ms | 256 KB |
1_015.txt | AC | 1 ms | 256 KB |
1_016.txt | AC | 1 ms | 256 KB |
1_017.txt | AC | 1 ms | 256 KB |
1_018.txt | AC | 1 ms | 256 KB |
1_019.txt | AC | 1 ms | 256 KB |
1_020.txt | AC | 1 ms | 256 KB |
1_021.txt | AC | 1 ms | 256 KB |
1_022.txt | AC | 1 ms | 256 KB |
1_023.txt | AC | 1 ms | 256 KB |
1_024.txt | AC | 1 ms | 256 KB |
1_025.txt | AC | 1 ms | 256 KB |
1_026.txt | AC | 1 ms | 256 KB |
1_027.txt | AC | 1 ms | 256 KB |
1_028.txt | AC | 1 ms | 256 KB |
1_029.txt | AC | 1 ms | 256 KB |
1_030.txt | AC | 1 ms | 256 KB |
1_031.txt | AC | 1 ms | 256 KB |
1_032.txt | AC | 1 ms | 256 KB |
1_033.txt | AC | 1 ms | 256 KB |
1_034.txt | AC | 1 ms | 256 KB |
1_035.txt | AC | 1 ms | 256 KB |
1_036.txt | AC | 1 ms | 256 KB |
1_037.txt | AC | 1 ms | 256 KB |
1_038.txt | AC | 1 ms | 256 KB |
1_039.txt | AC | 1 ms | 256 KB |
1_040.txt | AC | 1 ms | 256 KB |
1_041.txt | AC | 1 ms | 256 KB |
1_042.txt | AC | 1 ms | 256 KB |
1_043.txt | AC | 1 ms | 256 KB |
1_044.txt | AC | 1 ms | 256 KB |
1_045.txt | AC | 31 ms | 6396 KB |
1_046.txt | AC | 39 ms | 8700 KB |
1_047.txt | AC | 50 ms | 4476 KB |
1_048.txt | AC | 37 ms | 3964 KB |
1_049.txt | AC | 61 ms | 10876 KB |
1_050.txt | AC | 54 ms | 11132 KB |
1_051.txt | AC | 49 ms | 7932 KB |
1_052.txt | AC | 11 ms | 3580 KB |
1_053.txt | AC | 35 ms | 5500 KB |
1_054.txt | AC | 14 ms | 1660 KB |
1_055.txt | AC | 48 ms | 7672 KB |
1_056.txt | AC | 19 ms | 3708 KB |
1_057.txt | AC | 3 ms | 2428 KB |
1_058.txt | AC | 37 ms | 5628 KB |
1_059.txt | AC | 18 ms | 3452 KB |
1_060.txt | AC | 36 ms | 3196 KB |
1_061.txt | AC | 69 ms | 10876 KB |
1_062.txt | AC | 35 ms | 6268 KB |
1_063.txt | AC | 45 ms | 8060 KB |
1_064.txt | AC | 30 ms | 4092 KB |
1_065.txt | AC | 4 ms | 2556 KB |
1_066.txt | AC | 37 ms | 4348 KB |
1_067.txt | AC | 14 ms | 3324 KB |
1_068.txt | AC | 32 ms | 4348 KB |
1_069.txt | AC | 21 ms | 2428 KB |
1_070.txt | AC | 37 ms | 4604 KB |
1_071.txt | AC | 41 ms | 4344 KB |
1_072.txt | AC | 25 ms | 2172 KB |
1_073.txt | AC | 8 ms | 1020 KB |
1_074.txt | AC | 5 ms | 2556 KB |
1_075.txt | AC | 36 ms | 6780 KB |
1_076.txt | AC | 74 ms | 7932 KB |
1_077.txt | AC | 40 ms | 3448 KB |
1_078.txt | AC | 14 ms | 1404 KB |
1_079.txt | AC | 37 ms | 5756 KB |
1_080.txt | AC | 35 ms | 3580 KB |
1_081.txt | AC | 84 ms | 15384 KB |
1_082.txt | AC | 84 ms | 14616 KB |
1_083.txt | AC | 49 ms | 5912 KB |
1_084.txt | AC | 48 ms | 4732 KB |
1_085.txt | AC | 85 ms | 18200 KB |
1_086.txt | AC | 84 ms | 17944 KB |
1_087.txt | AC | 65 ms | 12028 KB |
1_088.txt | AC | 60 ms | 7292 KB |
1_089.txt | AC | 43 ms | 4988 KB |
1_090.txt | AC | 42 ms | 7676 KB |
1_091.txt | AC | 63 ms | 11516 KB |
1_092.txt | AC | 42 ms | 5884 KB |
1_093.txt | AC | 83 ms | 14104 KB |
1_094.txt | AC | 82 ms | 13464 KB |
1_095.txt | AC | 52 ms | 8060 KB |
1_096.txt | AC | 50 ms | 4120 KB |
1_097.txt | AC | 87 ms | 14616 KB |
1_098.txt | AC | 76 ms | 11032 KB |
1_099.txt | AC | 73 ms | 12024 KB |
1_100.txt | AC | 67 ms | 8312 KB |
1_101.txt | AC | 46 ms | 4216 KB |
1_102.txt | AC | 48 ms | 7164 KB |
1_103.txt | AC | 74 ms | 11256 KB |
1_104.txt | AC | 59 ms | 7416 KB |
1_105.txt | AC | 83 ms | 11416 KB |
1_106.txt | AC | 76 ms | 9112 KB |
1_107.txt | AC | 49 ms | 4248 KB |
1_108.txt | AC | 49 ms | 4604 KB |
1_109.txt | AC | 83 ms | 11544 KB |
1_110.txt | AC | 70 ms | 7576 KB |
1_111.txt | AC | 82 ms | 10520 KB |
1_112.txt | AC | 78 ms | 9112 KB |
1_113.txt | AC | 49 ms | 5116 KB |
1_114.txt | AC | 51 ms | 6780 KB |
1_115.txt | AC | 82 ms | 9752 KB |
1_116.txt | AC | 72 ms | 8728 KB |