結果
問題 | No.30 たこやき工場 |
ユーザー | te-sh |
提出日時 | 2020-01-23 11:52:32 |
言語 | D (dmd 2.106.1) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 9,429 bytes |
コンパイル時間 | 1,428 ms |
コンパイル使用メモリ | 148,844 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-22 04:25:58 |
合計ジャッジ時間 | 2,163 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 1 ms
6,940 KB |
testcase_04 | AC | 1 ms
6,944 KB |
testcase_05 | AC | 1 ms
6,940 KB |
testcase_06 | AC | 1 ms
6,944 KB |
testcase_07 | AC | 1 ms
6,940 KB |
testcase_08 | AC | 1 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 3 ms
6,940 KB |
testcase_11 | AC | 1 ms
6,944 KB |
testcase_12 | AC | 1 ms
6,940 KB |
testcase_13 | AC | 1 ms
6,940 KB |
testcase_14 | AC | 2 ms
6,940 KB |
testcase_15 | AC | 1 ms
6,940 KB |
testcase_16 | AC | 2 ms
6,940 KB |
ソースコード
// URL: https://ja.reactjs.org/tutorial/tutorial.html import std.algorithm, std.array, std.container, std.math, std.range, std.typecons, std.string; version(unittest) {} else void main() { int N; io.getV(N); auto g = Graph(N); auto p = new Vector!int[](N); foreach (i, ref pi; p) { pi = Vector!int(N); pi[i] = 1; } int M; io.getV(M); foreach (_; 0..M) { int P, Q, R; io.getV(P, Q, R); --P, --R; g.addEdge(R, P); p[R][R] = 0; p[R][P] = Q; } foreach_reverse (u; g.topologicalSort.nodes) { if (!g[u].empty) { auto q = Vector!int(N); foreach (v; g[u]) q += p[v]*p[u][v]; p[u] = q; } } foreach (i; 0..N-1) io.put(p[N-1][i]); } pure T isqrt(T)(T n) { static if (is(T == int)) auto max = 46341; else static if (is(T == long)) auto max = 3037000500L; auto bs = iota(T(0), max).map!(x => tuple(x, x^^2)).assumeSorted!"a[1]<=b[1]"; return bs.lowerBound(tuple(0, n)).back[0]; } pure T icbrt(T)(T n) { static if (is(T == int)) auto max = 1291; else static if (is(T == long)) auto max = 2097152L; auto bs = iota(T(0), max).map!(x => tuple(x, x^^3)).assumeSorted!"a[1]<=b[1]"; return bs.lowerBound(tuple(0, n)).back[0]; } pure T powr(alias pred = "a*b", T, U)(T a, U n, T one) { import std.functional; alias predFun = binaryFun!pred; if (n == 0) return one; auto r = one; for (; n > 0; n >>= 1) { if (n&1) r = predFun(r, a); a = predFun(a, a); } return r; } pure T powr(alias pred = "a*b", T, U)(T a, U n) { return powr!(pred, T, U)(a, n, T(1)); } pure T extGcd(T)(T a, T b, out T x, out T y) { auto g = a; x = 1; y = 0; if (b) { g = extGcd(b, a%b, y, x); y -= a/b*x; } return g; } struct Vector(T, T zero = 0) { alias V = Vector!(T, zero), Op = string; size_t n; @property T[] array() { return a; } alias array this; this(size_t n) in { assert(n > 0); } do { this.n = n; a = new T[](n); static if (T.init != zero) a[] = zero; } this(U)(U[] b) in { assert(b.length > 0); } do { n = b.length; static if (is(T == U)) a = b; else { a = new T[](n); foreach (i; 0..n) a[i] = b[i]; } } pure V dup() { auto b = V(n); b[] = a[]; return b; } pure V opBinary(Op op)(V b) if (op=="+"||op=="-") in { assert(n == b.n); } do { auto x = V(n); foreach (i; 0..n) x[i] = mixin("a[i]"~op~"b[i]"); return x; } ref V opOpAssign(Op op)(V b) if (op=="+"||op=="-") in { assert(n == b.n); } do { foreach (i; 0..n) mixin("a[i]"~op~"=b[i];"); return this; } pure V opBinary(Op op: "*")(T b) { auto x = V(n); foreach (i; 0..n) x[i] = a[i]*b; return x; } ref V opOpAssign(Op op: "*")(T b) { foreach (i; 0..n) a[i] *= b; return this; } pure T opBinary(Op op: "*")(V b) in { assert(n == b.n); } do { auto x = T(zero); foreach (i; 0..n) x += a[i]*b[i]; return x; } private T[] a; } Vector!(T, zero) vector(T, T zero = 0)(T[] a) { return Vector!(T, zero)(a); } Vector!(T, zero) vector(T, U, T zero = 0)(U[] a) if (!is(T == U)) { return Vector!(T, zero)(a); } pure T hypot2(T, alias zero)(Vector!(T, zero) a) { return a*a; } pure Vector!(T, zero) cross(T, alias zero)(Vector!(T, zero) a, Vector!(T, zero) b) in { assert(a.n == 3 && b.n == 3); } do { return Vector!(T, zero)([a[1]*b[2]-a[2]*b[1], a[2]*b[0]-a[0]*b[2], a[0]*b[1]-a[1]*b[0]]); } struct Matrix(T, T zero = 0, T one = 1) { alias M = Matrix!(T, zero, one), V = Vector!(T, zero), Op = string; size_t r, c; @property T[][] array() { return a; } alias array this; static auto unit(size_t n) in { assert(n > 0); } do { auto r = M(n, n); foreach (i; 0..n) r[i][i] = one; return r; } this(size_t r, size_t c) in { assert(r > 0 && c > 0); } do { this.r = r; this.c = c; a = new T[][](r, c); static if (T.init != zero) foreach (i; 0..r) a[i][] = zero; } this(U)(U[][] b) in { assert(b.length > 0 && b[0].length > 0 && b.all!(l => l.length == b[0].length)); } do { r = b.length; c = b[0].length; static if (is(T == U)) a = b; else { a = new T[][](r, c); foreach (i; 0..r) foreach (j; 0..c) a[i][j] = b[i][j]; } } pure M dup() { auto b = M(r, c); foreach (i; 0..r) b[i][] = a[i][]; return b; } pure bool opEquals(M b) { return r == b.r && c == b.c && zip(a, b.a).all!"a[0]==a[1]"; } pure M opBinary(Op op)(M b) if (op=="+"||op=="-") in { assert(r == b.r && c == b.c); } do { auto x = M(r, c); foreach (i; 0..r) foreach (j; 0..c) x[i][j] = mixin("a[i][j]"~op~"b[i][j]"); return x; } ref M opOpAssign(Op op)(M b) if (op=="+"||op=="-") in { assert(r == b.r && c == b.c); } do { foreach (i; 0..r) foreach (j; 0..c) mixin("a[i][j]"~op~"=b[i][j];"); return this; } pure M opBinary(Op op: "*")(T b) { auto x = M(r, c); foreach (i; 0..r) foreach (j; 0..c) x[i][j] = a[i][j]*b; return x; } ref M opOpAssign(Op op: "*")(T b) { foreach (i; 0..r) foreach (j; 0..c) a[i][j] *= b; return this; } pure M opBinary(Op op: "*")(M b) in { assert(c == b.r); } do { auto x = M(r, b.c); foreach (i; 0..r) foreach (j; 0..b.c) foreach (k; 0..c) x[i][j] += a[i][k]*b[k][j]; return x; } ref M opOpAssign(Op op: "*")(M b) in { assert(c == b.r); } do { auto x = this*b; r = x.r; c = x.c; a = x.a; return this; } pure V opBinary(Op op: "*")(V b) in { assert(c == b.n); } do { auto x = V(b.n); foreach (i; 0..r) foreach (j; 0..c) x[i] += a[i][j]*b[j]; return x; } pure M opBinary(Op op: "^^", U)(U n) in { assert(r == c); } do { return powr(this, n, M.unit(r)); } private T[][] a; } Matrix!(T, zero, one) matrix(T, T zero = 0, T one = 1)(T[][] a) { return Matrix!(T, zero, one)(a); } Matrix!(T, zero, one) matrix(T, U, T zero = 0, T one = 1)(U[][] a) if (!is(T == U)) { return Matrix!(T, zero, one)(a); } pure T det(T, alias zero, alias one)(Matrix!(T, zero, one) a) in { assert(a.r == a.c); } do { auto n = a.r, b = a.dup, d = one; foreach (i; 0..n) { auto p = i; foreach (j; i+1..n) if (b[p][i].abs < b[j][i].abs) p = j; swap(b[p], b[i]); foreach (j; i+1..n) foreach (k; i+1..n) b[j][k] -= b[i][k]*b[j][i]/b[i][i]; d *= b[i][i]; if (p != i) d = -d; } return d; } struct Graph { alias Node = int; Node n; Node[][] g; alias g this; this(Node n) { this.n = n; g = new Node[][](n); } void addEdge(Node u, Node v) { g[u] ~= v; } void addEdgeB(Node u, Node v) { g[u] ~= v; g[v] ~= u; } } struct GraphW(W = int, W i = 10^^9) { alias Node = int, Wt = W, inf = i; struct Edge { Node src, dst; Wt wt; alias cap = wt; } Node n; Edge[][] g; alias g this; this(Node n) { this.n = n; g = new Edge[][](n); } void addEdge(Node u, Node v, Wt w) { g[u] ~= Edge(u, v, w); } void addEdgeB(Node u, Node v, Wt w) { g[u] ~= Edge(u, v, w); g[v] ~= Edge(v, u, w); } } struct GraphM(W = int, W i = 10^^9) { alias Node = int, Wt = W, inf = i; Node n; Wt[][] g; alias g this; this(int n) { this.n = n; g = new Wt[][](n, n); } static GraphM!(W, i) init(Node n) { auto g = GraphM!(W, i)(n); foreach (i; 0..n) { g[i][] = inf; g[i][i] = 0; } return g; } } struct TopologicalSort(Graph) { alias Node = Graph.Node; Graph g; alias g this; Node[] nodes; this(Graph g) { this.g = g; auto h = new int[](n); foreach (u; 0..n) foreach (v; g[u]) ++h[v]; auto st = SList!Node(); foreach (i; 0..n) if (h[i] == 0) st.insertFront(i); while (!st.empty()) { auto u = st.front; st.removeFront(); nodes ~= u; foreach (v; g[u]) { --h[v]; if (h[v] == 0) st.insertFront(v); } } } pure bool hasCycle() { return nodes.length != n; } } TopologicalSort!(Graph) topologicalSort(Graph)(Graph g) { return TopologicalSort!Graph(g); } auto io = IO!()(); import std.stdio; struct IO(string floatFormat = "%.10f", string delimiter = " ", alias IN = stdin, alias OUT = stdout) { import std.conv, std.format, std.meta, std.traits; alias assignable = hasAssignableElements; auto getV(T...)(ref T v) { foreach (ref w; v) get(w); } auto getA(T)(size_t n, ref T v) if (assignable!T) { v = new T(n); foreach (ref w; v) get(w); } auto getC(T...)(size_t n, ref T v) if (allSatisfy!(assignable, T)) { foreach (ref w; v) w = new typeof(w)(n); foreach (i; 0..n) foreach (ref w; v) get(w[i]); } auto getM(T)(size_t r, size_t c, ref T v) if (assignable!T && assignable!(ElementType!T)) { v = new T(r); foreach (ref w; v) getA(c, w); } auto put(bool flush = false, T...)(T v) { foreach (i, w; v) { putA(w); if (i < v.length-1) OUT.write(delimiter); } OUT.writeln; static if (flush) OUT.flush(); } auto putB(S, T)(bool c, S t, T f) { if (c) put(t); else put(f); } auto putRaw(T...)(T v) { OUT.write(v); OUT.writeln; } private { dchar[] buf; auto sp = (new dchar[](0)).splitter; void nextLine() { IN.readln(buf); sp = buf.splitter; } auto get(T)(ref T v) { if (sp.empty) nextLine(); v = sp.front.to!T; sp.popFront(); } auto putR(T)(T v) { auto w = v; while (!w.empty) { putA(w.front); w.popFront(); if (!w.empty) OUT.write(delimiter); } } auto putA(T)(T v) { static if (isInputRange!T && !isSomeString!T) putR(v); else if (isFloatingPoint!T) OUT.write(format(floatFormat, v)); else OUT.write(v); } } }