Submission #1059994
Source Code Expand
/+ dub.sdl:
name "A"
dependency "dcomp" version=">=0.4.0"
+/
import std.stdio, std.algorithm, std.conv, std.range;
import std.typecons;
// import dcomp.scanner, dcomp.container.deque;
int main() {
auto sc = new Scanner(stdin);
alias E = Tuple!(int, "to");
int n;
sc.read(n);
E[][] g = new E[][2*n-1];
foreach (i; 0..n-1) {
int a, b;
sc.read(a, b); a--; b--;
g[a] ~= E(n+i);
g[n+i] ~= E(a);
g[b] ~= E(n+i);
g[n+i] ~= E(b);
}
string s;
sc.read(s);
n = 2*n-1;
int[2] searchMid() {
int[] rt = new int[n];
int[2] lng;
void dfs(int p, int b, int dps = 0) {
rt[p] = b;
if (lng[1] < dps) {
lng = [p, dps];
}
foreach (e; g[p]) {
int d = e.to;
if (d == b) continue;
dfs(d, p, dps+1);
}
}
lng = [-1, -1];
dfs(0, -1);
int v = lng[0];
lng = [-1, -1];
dfs(v, -1);
int[] path;
int u = lng[0];
while (u != v) {
path ~= u;
u = rt[u];
}
path ~= v;
// writeln(path);
return [path[path.length/2], path.length.to!int/2];
}
int[2] mid = searchMid();
// writeln(mid);
bool[] bc = new bool[n];
bool[] bsm = new bool[n];
int[] md = new int[n];
void dfs(int p, int b) {
if (p < (n+1)/2 && s[p] == '1') bc[p] = true;
bsm[p] = bc[p];
md[p] = 0;
foreach (e; g[p]) {
int d = e.to;
if (d == b) continue;
dfs(d, p);
bsm[p] |= bsm[d];
md[p] = max(md[p], md[d]+1);
}
}
dfs(mid[0], -1);
/* writeln(bc);
writeln(bsm);
writeln(md);*/
long ans = 0;
int calc(int p, int b) {
int mi = 10^^9;
foreach (e; g[p]) {
int d = e.to;
if (d == b) continue;
mi = min(mi, 1+calc(d, p));
}
int di = md[p];
if (bc[p]) {
ans += di/2+1;
return di;
} else {
if (mi < 10^^8) {
ans += (di-mi)/2+1;
return di;
}
return mi;
}
}
calc(mid[0], -1);
writeln(ans);
return 0;
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/container/deque.d */
// module dcomp.container.deque;
struct Deque(T) {
import core.exception : RangeError;
import core.memory : GC;
import std.range : ElementType, isInputRange;
import std.traits : isImplicitlyConvertible;
struct Payload {
T *d;
size_t st, length, cap;
@property bool empty() const { return length == 0; }
alias opDollar = length;
ref inout(T) opIndex(size_t i) inout {
version(assert) if (length <= i) throw new RangeError();
return d[(st+i >= cap) ? (st+i-cap) : st+i];
}
private void expand() {
import std.algorithm : max;
assert(length == cap);
auto nc = max(4L, 2*cap);
T* nd = cast(T*)GC.malloc(nc * T.sizeof);
foreach (i; 0..length) {
nd[i] = this[i];
}
d = nd; st = 0; cap = nc;
}
void insertFront(T v) {
if (length == cap) expand();
if (st == 0) st += cap;
st--; length++;
this[0] = v;
}
void insertBack(T v) {
if (length == cap) expand();
length++;
this[length-1] = v;
}
void removeFront() {
assert(!empty, "Deque.removeFront: Deque is empty");
st++; length--;
if (st == cap) st = 0;
}
void removeBack() {
assert(!empty, "Deque.removeBack: Deque is empty");
length--;
}
}
struct RangeT(A) {
alias T = typeof(*(A.p));
alias E = typeof(A.p.d[0]);
T *p;
size_t a, b;
@property bool empty() const { return b <= a; }
@property size_t length() const { return b-a; }
@property RangeT save() { return RangeT(p, a, b); }
@property RangeT!(const A) save() const {
return typeof(return)(p, a, b);
}
alias opDollar = length;
@property ref inout(E) front() inout { return (*p)[a]; }
@property ref inout(E) back() inout { return (*p)[b-1]; }
void popFront() {
version(assert) if (empty) throw new RangeError();
a++;
}
void popBack() {
version(assert) if (empty) throw new RangeError();
b--;
}
ref inout(E) opIndex(size_t i) inout { return (*p)[i]; }
RangeT opSlice() { return this.save; }
RangeT opSlice(size_t i, size_t j) {
version(assert) if (i > j || a + j > b) throw new RangeError();
return typeof(return)(p, a+i, a+j);
}
RangeT!(const A) opSlice() const { return this.save; }
RangeT!(const A) opSlice(size_t i, size_t j) const {
version(assert) if (i > j || a + j > b) throw new RangeError();
return typeof(return)(p, a+i, a+j);
}
}
alias Range = RangeT!Deque;
alias ConstRange = RangeT!(const Deque);
alias ImmutableRange = RangeT!(immutable Deque);
Payload *p;
private void I() { if (!p) p = new Payload(); }
private void C() const { assert(p, "this deque is not init"); }
//some value
this(U)(U[] values...) if (isImplicitlyConvertible!(U, T)) {I;
p = new Payload();
foreach (v; values) {
insertBack(v);
}
}
//range
this(Range)(Range r)
if (isInputRange!Range &&
isImplicitlyConvertible!(ElementType!Range, T) &&
!is(Range == T[])) {I;
p = new Payload();
foreach (v; r) {
insertBack(v);
}
}
@property bool empty() const { return (!p || p.empty); }
@property size_t length() const { return (p ? p.length : 0); }
alias opDollar = length;
ref inout(T) opIndex(size_t i) inout {C; return (*p)[i]; }
ref inout(T) front() inout {C; return (*p)[0]; }
ref inout(T) back() inout {C; return (*p)[$-1]; }
void insertFront(T v) {I; p.insertFront(v); }
void insertBack(T v) {I; p.insertBack(v); }
void removeFront() {C; p.removeFront(); }
void removeBack() {C; p.removeBack(); }
Range opSlice() {I; return Range(p, 0, length); }
}
unittest {
import std.algorithm : equal;
import std.range.primitives : isRandomAccessRange;
import std.container.util : make;
auto q = make!(Deque!int);
assert(isRandomAccessRange!(typeof(q[])));
//insert,remove
assert(equal(q[], new int[](0)));
q.insertBack(1);
assert(equal(q[], [1]));
q.insertBack(2);
assert(equal(q[], [1, 2]));
q.insertFront(3);
assert(equal(q[], [3, 1, 2]) && q.front == 3);
q.removeFront;
assert(equal(q[], [1, 2]) && q.length == 2);
q.insertBack(4);
assert(equal(q[], [1, 2, 4]) && q.front == 1 && q.back == 4 && q[$-1] == 4);
q.insertFront(5);
assert(equal(q[], [5, 1, 2, 4]));
//range
assert(equal(q[][1..3], [1, 2]));
assert(equal(q[][][][], q[]));
//const range
const auto rng = q[];
assert(rng.front == 5 && rng.back == 4);
//reference type
auto q2 = q;
q2.insertBack(6);
q2.insertFront(7);
assert(equal(q[], q2[]) && q.length == q2.length);
//construct with make
auto a = make!(Deque!int)(1, 2, 3);
auto b = make!(Deque!int)([1, 2, 3]);
assert(equal(a[], b[]));
}
unittest {
Deque!int a;
Deque!int b;
a.insertFront(2);
assert(b.length == 0);
}
unittest {
import std.algorithm : equal;
import std.range : iota;
Deque!int a;
foreach (i; 0..100) {
a.insertBack(i);
}
assert(equal(a[], iota(100)));
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/scanner.d */
// module dcomp.scanner;
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;
}
string[] buf;
private bool succ() {
while (!buf.length) {
if (f.eof) return false;
buf = f.readln.split;
}
return true;
}
private bool readSingle(T)(ref T x) {
if (!succ()) return false;
static if (isArray!T) {
alias E = ElementType!T;
static if (isSomeChar!E) {
//string or char[10] etc
x = buf.front;
buf.popFront;
} else {
static if (isStaticArray!T) {
//static
assert(buf.length == T.length);
}
x = buf.map!(to!E).array;
buf.length = 0;
}
} else {
x = buf.front.to!T;
buf.popFront;
}
return true;
}
int read(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);
}
}
}
unittest {
import std.path : buildPath;
import std.file : tempDir;
import std.algorithm : equal;
import std.stdio : File;
string fileName = buildPath(tempDir, "kyuridenanmaida.txt");
auto fout = File(fileName, "w");
fout.writeln("1 2 3");
fout.writeln("ab cde");
fout.writeln("1.0 1.0 2.0");
fout.close;
Scanner sc = new Scanner(File(fileName, "r"));
int a;
int[2] b;
char[2] c;
string d;
double e;
double[] f;
sc.read(a, b, c, d, e, f);
assert(a == 1);
assert(equal(b[], [2, 3]));
assert(equal(c[], "ab"));
assert(equal(d, "cde"));
assert(e == 1.0);
assert(equal(f, [1.0, 2.0]));
}
Submission Info
Submission Time |
|
Task |
F - Black Radius |
User |
yosupo |
Language |
D (LDC 0.17.0) |
Score |
1900 |
Code Size |
10532 Byte |
Status |
AC |
Exec Time |
588 ms |
Memory |
56248 KB |
Judge Result
Set Name |
Sample |
Subtask |
All |
Score / Max Score |
0 / 0 |
1300 / 1300 |
600 / 600 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt |
Subtask |
0_01.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt, 2_16.txt, 2_17.txt, 2_18.txt, 2_19.txt, 2_20.txt, 2_21.txt, 2_22.txt, 2_23.txt, 2_24.txt, 2_25.txt, 2_26.txt, 2_27.txt, 2_28.txt, 2_29.txt, 2_30.txt, 2_31.txt, 2_32.txt, 2_33.txt, 2_34.txt, 2_35.txt, 2_36.txt, 2_37.txt, 2_38.txt, 2_39.txt, 2_40.txt, 2_41.txt, 2_42.txt, 2_43.txt, 2_44.txt, 2_45.txt, 2_46.txt, 2_47.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
2 ms |
256 KB |
0_01.txt |
AC |
2 ms |
256 KB |
0_02.txt |
AC |
2 ms |
256 KB |
1_00.txt |
AC |
2 ms |
256 KB |
1_01.txt |
AC |
537 ms |
56248 KB |
1_02.txt |
AC |
483 ms |
46136 KB |
1_03.txt |
AC |
352 ms |
28472 KB |
1_04.txt |
AC |
337 ms |
28196 KB |
1_05.txt |
AC |
265 ms |
27784 KB |
1_06.txt |
AC |
482 ms |
29752 KB |
1_07.txt |
AC |
416 ms |
29752 KB |
1_08.txt |
AC |
376 ms |
32312 KB |
1_09.txt |
AC |
460 ms |
42040 KB |
1_10.txt |
AC |
453 ms |
44812 KB |
1_11.txt |
AC |
520 ms |
51984 KB |
1_12.txt |
AC |
381 ms |
36152 KB |
1_13.txt |
AC |
427 ms |
39460 KB |
1_14.txt |
AC |
392 ms |
33936 KB |
1_15.txt |
AC |
395 ms |
33976 KB |
1_16.txt |
AC |
437 ms |
37816 KB |
1_17.txt |
AC |
481 ms |
42680 KB |
1_18.txt |
AC |
381 ms |
29752 KB |
1_19.txt |
AC |
350 ms |
29624 KB |
1_20.txt |
AC |
344 ms |
28344 KB |
1_21.txt |
AC |
373 ms |
29992 KB |
1_22.txt |
AC |
333 ms |
29952 KB |
1_23.txt |
AC |
338 ms |
29832 KB |
1_24.txt |
AC |
368 ms |
32000 KB |
1_25.txt |
AC |
381 ms |
31672 KB |
1_26.txt |
AC |
336 ms |
29604 KB |
1_27.txt |
AC |
324 ms |
30008 KB |
1_28.txt |
AC |
348 ms |
28984 KB |
1_29.txt |
AC |
369 ms |
37172 KB |
2_00.txt |
AC |
2 ms |
256 KB |
2_01.txt |
AC |
540 ms |
56248 KB |
2_02.txt |
AC |
548 ms |
56248 KB |
2_03.txt |
AC |
588 ms |
56248 KB |
2_04.txt |
AC |
503 ms |
46136 KB |
2_05.txt |
AC |
516 ms |
46136 KB |
2_06.txt |
AC |
504 ms |
46136 KB |
2_07.txt |
AC |
368 ms |
28472 KB |
2_08.txt |
AC |
382 ms |
28472 KB |
2_09.txt |
AC |
351 ms |
28472 KB |
2_10.txt |
AC |
317 ms |
28280 KB |
2_11.txt |
AC |
324 ms |
28280 KB |
2_12.txt |
AC |
307 ms |
28276 KB |
2_13.txt |
AC |
269 ms |
27704 KB |
2_14.txt |
AC |
263 ms |
27808 KB |
2_15.txt |
AC |
262 ms |
27808 KB |
2_16.txt |
AC |
407 ms |
29684 KB |
2_17.txt |
AC |
369 ms |
29752 KB |
2_18.txt |
AC |
375 ms |
29752 KB |
2_19.txt |
AC |
354 ms |
29752 KB |
2_20.txt |
AC |
365 ms |
29752 KB |
2_21.txt |
AC |
359 ms |
29752 KB |
2_22.txt |
AC |
369 ms |
32312 KB |
2_23.txt |
AC |
372 ms |
32312 KB |
2_24.txt |
AC |
380 ms |
32312 KB |
2_25.txt |
AC |
443 ms |
42040 KB |
2_26.txt |
AC |
434 ms |
42040 KB |
2_27.txt |
AC |
446 ms |
42040 KB |
2_28.txt |
AC |
453 ms |
40632 KB |
2_29.txt |
AC |
516 ms |
54712 KB |
2_30.txt |
AC |
479 ms |
46136 KB |
2_31.txt |
AC |
453 ms |
43132 KB |
2_32.txt |
AC |
380 ms |
30756 KB |
2_33.txt |
AC |
403 ms |
34552 KB |
2_34.txt |
AC |
425 ms |
38144 KB |
2_35.txt |
AC |
497 ms |
43068 KB |
2_36.txt |
AC |
346 ms |
28088 KB |
2_37.txt |
AC |
355 ms |
29752 KB |
2_38.txt |
AC |
375 ms |
31528 KB |
2_39.txt |
AC |
348 ms |
28688 KB |
2_40.txt |
AC |
330 ms |
29968 KB |
2_41.txt |
AC |
356 ms |
29748 KB |
2_42.txt |
AC |
347 ms |
27544 KB |
2_43.txt |
AC |
405 ms |
38420 KB |
2_44.txt |
AC |
317 ms |
29980 KB |
2_45.txt |
AC |
299 ms |
27960 KB |
2_46.txt |
AC |
278 ms |
28444 KB |
2_47.txt |
AC |
366 ms |
36020 KB |