Submission #1708124
Source Code Expand
/+ dub.sdl:
name "A"
dependency "dcomp" version=">=0.7.4"
+/
import std.stdio, std.algorithm, std.range, std.conv;
// import dcomp.foundation, dcomp.scanner;
import std.typecons;
// import dcomp.algorithm;
// import dcomp.container.pairingheap;
int main() {
auto sc = new Scanner(stdin);
int n, k;
sc.read(n, k);
alias E = Tuple!(int, "to", int, "dist");
E[][] g = new E[][](n);
foreach (i; 0..n-1) {
int a, b, c;
sc.read(a, b, c); a--; b--;
g[a] ~= E(b, c);
g[b] ~= E(a, c);
}
int[] par = new int[n];
par[0] = -1;
int[] dps = new int[n];
dps[0] = 0;
bool[] vis = new bool[n];
int[] li;
PairingHeap!(int[2], "a[1] > b[1]") q;
q.insert([0, 0]);
while (!q.empty) {
int[2] p = q.front; q.removeFront;
vis[p[0]] = true;
li ~= p[0];
foreach (e; g[p[0]]) {
if (vis[e.to]) continue;
par[e.to] = p[0];
dps[e.to] = p[1] + e.dist;
q.insert([e.to, p[1] + e.dist]);
}
}
// writeln(li);
int[] near = new int[n];
/* void mark(int p, int d) {
near[p] = d;
foreach (e; g[p]) {
if (d - e.dist <= near[e.to]) continue;
mark(e.to, d - e.dist);
}
}*/
bool check(int md) {
PairingHeap!(int[2], "a[1] < b[1]") q;
near[] = 0;
int cnt = 0;
foreach_reverse (p; li) {
if (near[p] > 0) continue;
while (!q.empty && q.front[1] >= dps[p]) {
auto w = q.front; q.removeFront;
int d = w[1] - dps[w[0]];
if (d < near[w[0]]) continue;
foreach (e; g[w[0]]) {
if (d - e.dist <= near[e.to]) continue;
near[e.to] = d - e.dist;
q.insert([e.to, near[e.to] + dps[e.to]]);
}
}
if (near[p] > 0) continue;
cnt++;
near[p] = md;
q.insert([p, near[p] + dps[p]]);
// mark(p, md);
}
return k <= cnt;
}
writeln(binSearch!(x => !check(x))(1, 10^^9) - 1);
return 0;
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/container/pairingheap.d */
// module dcomp.container.pairingheap;
struct PairingHeapPayload(T, alias opCmp) {
import std.range : iota;
import std.algorithm : swap;
alias NP = Node*;
static struct Node {
T d;
NP head, next;
this(T d) {
this.d = d;
}
}
NP n;
size_t length;
bool empty() const { return length == 0; }
static NP merge(NP x, NP y) {
if (!x) return y;
if (!y) return x;
if (opCmp(x.d, y.d)) swap(x, y);
y.next = x.head;
x.head = y;
return x;
}
void insert(T x) {
length++;
if (!n) n = new Node(x);
else n = merge(n, new Node(x));
}
T front() const {
assert(n);
return n.d;
}
void removeFront() {
assert(n);
assert(length > 0);
length--;
NP x;
NP s = n.head;
while (s) {
NP a, b;
a = s; s = s.next; a.next = null;
if (s) {
b = s; s = s.next; b.next = null;
}
a = merge(a, b);
assert(a);
if (!x) x = a;
else {
a.next = x.next;
x.next = a;
}
}
n = null;
while (x) {
NP a = x; x = x.next;
n = merge(a, n);
}
}
}
struct PairingHeap(T, alias _opCmp) {
import std.stdio;
import std.functional : binaryFun;
alias opCmp = binaryFun!_opCmp;
alias Payload = PairingHeapPayload!(T, opCmp);
Payload* p;
void I() { if (!p) p = new Payload(); }
bool empty() const { return !p || p.empty(); }
size_t length() const { return (!p) ? 0 : p.length; }
void insert(T x) {
I();
assert(p);
p.insert(x);
}
T front() const {
assert(p);
return p.front;
}
void removeFront() {
assert(p);
p.removeFront;
}
void meld(PairingHeap r) {
p.length += r.p.length;
p.n = Payload.merge(p.n, r.p.n);
r.p.n = null;
}
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/foundation.d */
// module dcomp.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/dcomp/source/dcomp/scanner.d */
// module dcomp.scanner;
// import dcomp.array;
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 {
FastAppender!(E[]) buf;
while (succW()) {
buf ~= line.parse!E;
}
x = buf.data;
}
} else {
x = line.parse!T;
}
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);
}
}
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/algorithm.d */
// module dcomp.algorithm;
import std.range.primitives;
import std.traits : isFloatingPoint, isIntegral;
T binSearch(alias pred, T)(T l, T r) if (isIntegral!T) {
while (r-l > 1) {
T md = (l+r)/2;
if (!pred(md)) l = md;
else r = md;
}
return r;
}
T binSearch(alias pred, T)(T l, T r, int cnt = 60) if (isFloatingPoint!T) {
foreach (i; 0..cnt) {
T md = (l+r)/2;
if (!pred(md)) l = md;
else r = md;
}
return r;
}
E minimum(alias pred = "a < b", Range, E = ElementType!Range)(Range range, E seed)
if (isInputRange!Range && !isInfinite!Range) {
import std.algorithm, std.functional;
return reduce!((a, b) => binaryFun!pred(a, b) ? a : b)(seed, range);
}
ElementType!Range minimum(alias pred = "a < b", Range)(Range range) {
assert(!range.empty, "range must not empty");
auto e = range.front; range.popFront;
return minimum!pred(range, e);
}
E maximum(alias pred = "a < b", Range, E = ElementType!Range)(Range range, E seed)
if (isInputRange!Range && !isInfinite!Range) {
import std.algorithm, std.functional;
return reduce!((a, b) => binaryFun!pred(a, b) ? b : a)(seed, range);
}
ElementType!Range maximum(alias pred = "a < b", Range)(Range range) {
assert(!range.empty, "range must not empty");
auto e = range.front; range.popFront;
return maximum!pred(range, e);
}
Rotator!Range rotator(Range)(Range r) {
return Rotator!Range(r);
}
struct Rotator(Range)
if (isForwardRange!Range && hasLength!Range) {
size_t cnt;
Range start, now;
this(Range r) {
cnt = 0;
start = r.save;
now = r.save;
}
this(this) {
start = start.save;
now = now.save;
}
@property bool empty() {
return now.empty;
}
@property auto front() {
assert(!now.empty);
import std.range : take, chain;
return chain(now, start.take(cnt));
}
@property Rotator!Range save() {
return this;
}
void popFront() {
cnt++;
now.popFront;
}
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/array.d */
// module dcomp.array;
T[N] fixed(T, size_t N)(T[N] a) {return a;}
struct FastAppender(A, size_t MIN = 4) {
import std.algorithm : max;
import std.conv;
import std.range.primitives : ElementEncodingType;
import core.stdc.string : memcpy;
private alias T = ElementEncodingType!A;
private T* _data;
private uint len, cap;
@property size_t length() const {return len;}
bool empty() const { return len == 0; }
void reserve(size_t nlen) {
import core.memory : GC;
if (nlen <= cap) return;
void* nx = GC.malloc(nlen * T.sizeof);
cap = nlen.to!uint;
if (len) memcpy(nx, _data, len * T.sizeof);
_data = cast(T*)(nx);
}
void free() {
import core.memory : GC;
GC.free(_data);
}
void opOpAssign(string op : "~")(T item) {
if (len == cap) {
reserve(max(MIN, cap*2));
}
_data[len++] = item;
}
void insertBack(T item) {
this ~= item;
}
void removeBack() {
len--;
}
void clear() {
len = 0;
}
ref inout(T) back() inout { assert(len); return _data[len-1]; }
ref inout(T) opIndex(size_t i) inout { return _data[i]; }
T[] data() {
return (_data) ? _data[0..len] : null;
}
}
/*
This source code generated by dcomp and include dcomp's source code.
dcomp's Copyright: Copyright (c) 2016- Kohei Morita. (https://github.com/yosupo06/dcomp)
dcomp's License: MIT License(https://github.com/yosupo06/dcomp/blob/master/LICENSE.txt)
*/
Submission Info
Submission Time |
|
Task |
H - High-powered Illuminations |
User |
yosupo |
Language |
D (LDC 0.17.0) |
Score |
100 |
Code Size |
11657 Byte |
Status |
AC |
Exec Time |
1464 ms |
Memory |
33660 KB |
Judge Result
Set Name |
sample |
dataset1 |
dataset2 |
Score / Max Score |
0 / 0 |
50 / 50 |
50 / 50 |
Status |
|
|
|
Set Name |
Test Cases |
sample |
sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt |
dataset1 |
sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt |
dataset2 |
sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 02-20.txt, 02-21.txt, 02-22.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
1 ms |
256 KB |
01-02.txt |
AC |
234 ms |
10108 KB |
01-03.txt |
AC |
226 ms |
10748 KB |
01-04.txt |
AC |
218 ms |
11004 KB |
01-05.txt |
AC |
221 ms |
11004 KB |
01-06.txt |
AC |
215 ms |
9980 KB |
01-07.txt |
AC |
230 ms |
9980 KB |
01-08.txt |
AC |
243 ms |
11132 KB |
01-09.txt |
AC |
232 ms |
11900 KB |
01-10.txt |
AC |
223 ms |
11260 KB |
01-11.txt |
AC |
204 ms |
9980 KB |
01-12.txt |
AC |
207 ms |
11260 KB |
01-13.txt |
AC |
168 ms |
12156 KB |
01-14.txt |
AC |
173 ms |
12156 KB |
01-15.txt |
AC |
174 ms |
12156 KB |
01-16.txt |
AC |
211 ms |
10876 KB |
01-17.txt |
AC |
178 ms |
9980 KB |
01-18.txt |
AC |
196 ms |
11900 KB |
01-19.txt |
AC |
192 ms |
10236 KB |
01-20.txt |
AC |
187 ms |
11516 KB |
01-21.txt |
AC |
168 ms |
11260 KB |
01-22.txt |
AC |
191 ms |
10108 KB |
02-01.txt |
AC |
1250 ms |
30076 KB |
02-02.txt |
AC |
1238 ms |
31228 KB |
02-03.txt |
AC |
1224 ms |
30716 KB |
02-04.txt |
AC |
1291 ms |
30204 KB |
02-05.txt |
AC |
1463 ms |
30716 KB |
02-06.txt |
AC |
1207 ms |
30204 KB |
02-07.txt |
AC |
1263 ms |
29436 KB |
02-08.txt |
AC |
1188 ms |
30588 KB |
02-09.txt |
AC |
1306 ms |
30588 KB |
02-10.txt |
AC |
1464 ms |
30972 KB |
02-11.txt |
AC |
1320 ms |
31228 KB |
02-12.txt |
AC |
1169 ms |
30588 KB |
02-13.txt |
AC |
1133 ms |
30716 KB |
02-14.txt |
AC |
927 ms |
32892 KB |
02-15.txt |
AC |
939 ms |
32764 KB |
02-16.txt |
AC |
1051 ms |
33660 KB |
02-17.txt |
AC |
977 ms |
27004 KB |
02-18.txt |
AC |
1052 ms |
26364 KB |
02-19.txt |
AC |
1108 ms |
31100 KB |
02-20.txt |
AC |
963 ms |
32380 KB |
02-21.txt |
AC |
1070 ms |
31612 KB |
02-22.txt |
AC |
967 ms |
28028 KB |
sample-01.txt |
AC |
1 ms |
256 KB |
sample-02.txt |
AC |
1 ms |
256 KB |
sample-03.txt |
AC |
1 ms |
256 KB |
sample-04.txt |
AC |
1 ms |
256 KB |