結果

問題 No.177 制作進行の宮森あおいです！
コンテスト
ユーザー te-sh
提出日時 2020-02-21 18:52:45
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 6,405 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 927 ms
コンパイル使用メモリ 116,744 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-22 05:21:14
合計ジャッジ時間 1,496 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.d(286): Deprecation: function `Main.IO!(makeGlobal, makeGlobal).IO.put!("{}", string).put.putMain!(c, string).putMain` function requires a dual-context, which is deprecated
Main.d-mixin-256(256):        instantiated from here: `putMain!(c, string)`
Main.d(260):        instantiated from here: `put!("{}", string)`
Main.d(28):        instantiated from here: `putB!("{}", string, string)`

ソースコード

diff #
raw source code 

// URL: https://yukicoder.me/problems/no/177

import std.algorithm, std.array, std.bitmanip, std.container, std.conv, std.format,
       std.functional, std.math, std.range, std.traits, std.typecons, std.stdio, std.string;

version(unittest) {} else
void main()
{
  int W; io.getV(W);
  int N; io.getV(N);
  int[] J; io.getA(N, J);
  int M; io.getV(M);
  int[] C; io.getA(M, C);

  auto g = GraphW!int(N+M+2), s = N+M, t = N+M+1;
  foreach (i; 0..N) g.addEdge(s, i, J[i]);
  foreach (i; 0..M) g.addEdge(N+i, t, C[i]);

  foreach (i; 0..M) {
    int Q; io.getV(Q);
    int[] X; io.getA(Q, X); --X[];

    foreach (k; 0..N)
      if (!X.canFind(k))
        g.addEdge(k, N+i, g.inf);
  }

  io.putB(g.dinic(s, t).flow >= W, "SHIROBAKO", "BANSAKUTSUKITA");
}

struct Graph
{
  alias Node = int;
  Node n;
  Node[][] g;
  alias g this;

  pure nothrow @safe
  {
    this(Node n)
    {
      this.n = n;
      g = new Node[][](n);
    }
    void addEdge(Node u, Node v)
      in { assert(0 <= u && u < n && 0 <= v && v < n); }
    do
    {
      g[u] ~= v;
    }
    void addEdgeB(Node u, Node v)
      in { assert(0 <= u && u < n && 0 <= v && v < n); }
    do
    {
      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;

  pure nothrow @safe
  {
    this(Node n)
    {
      this.n = n;
      g = new Edge[][](n);
    }
    void addEdge(Node u, Node v, Wt w)
      in { assert(0 <= u && u < n && 0 <= v && v < n); }
    do
    {
      g[u] ~= Edge(u, v, w);
    }
    void addEdgeB(Node u, Node v, Wt w)
      in { assert(0 <= u && u < n && 0 <= v && v < n); }
    do
    {
      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;

  pure nothrow @safe
  {
    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 Dinic(Graph)
{
  alias Node = Graph.Node, Wt = Graph.Wt;
  Graph g;
  alias g this;
  Wt flow = 0;

  pure nothrow @safe
  {
    this(Graph g, Node s, Node t)
      in { assert(0 <= s && s < g.n && 0 <= t && t < g.n); }
    do
    {
      this.g = g;
      auto adj = withRev(), level = new int[](n);

      auto levelize()
      {
        level[] = -1; level[s] = 0;

        auto q = DList!Node(s);
        while (!q.empty) {
          auto u = q.front; q.removeFront();
          if (u == t) break;
          foreach (ref e; adj[u])
            if (e.cap > e.flow && level[e.dst] < 0) {
              q.insertBack(e.dst);
              level[e.dst] = level[u] + 1;
            }
        }

        return level[t];
      }

      Wt augment(Node u, Wt cur)
      {
        if (u == t) return cur;

        foreach (ref e; adj[u]) {
          auto r = &adj[e.dst][e.rev];
          if (e.cap > e.flow && level[u] < level[e.dst]) {
            auto f = augment(e.dst, min(cur, e.cap - e.flow));
            if (f > 0) {
              e.flow += f;
              r.flow -= f;
              return f;
            }
          }
        }

        return 0;
      }

      Wt f = 0;
      while (levelize >= 0)
        while ((f = augment(s, g.inf)) > 0)
          flow += f;
    }
  }

  private
  {
    struct EdgeR { Node src, dst; Wt cap, flow; Node rev; }

    pure nothrow @safe
    {
      EdgeR[][] withRev() const
      {
        auto r = new EdgeR[][](n);
        foreach (gi; g)
          foreach (e; gi) {
            r[e.src] ~= EdgeR(e.src, e.dst, e.cap, 0, cast(Node)(r[e.dst].length));
            r[e.dst] ~= EdgeR(e.dst, e.src, 0, 0, cast(Node)(r[e.src].length) - 1);
          }
        return r;
      }
    }
  }
}

pure nothrow @safe
{
  auto dinic(Graph, Node)(Graph g, Node s, Node t)
    in { assert(0 <= s && s < g.n && 0 <= t && t < g.n); }
  do
  {
    return Dinic!Graph(g, s, t);
  }
}

auto io = IO!()();
import std.stdio;
struct IO(alias IN = stdin, alias OUT = stdout)
{
  import std.meta : allSatisfy;
  import core.stdc.stdlib : exit;

  void getV(T...)(ref T v)
  {
    foreach (ref w; v) get(w);
  }
  void getA(T)(size_t n, ref T v)
    if (hasAssignableElements!T)
  {
    v = new T(n);
    foreach (ref w; v) get(w);
  }
  void getC(T...)(size_t n, ref T v)
    if (allSatisfy!(hasAssignableElements, T))
  {
    foreach (ref w; v) w = new typeof(w)(n);
    foreach (i; 0..n) foreach (ref w; v) get(w[i]);
  }
  void getM(T)(size_t r, size_t c, ref T v)
    if (hasAssignableElements!T && hasAssignableElements!(ElementType!T))
  {
    v = new T(r);
    foreach (ref w; v) getA(c, w);
  }
  template getS(E...)
  {
    void getS(T)(size_t n, ref T v)
    {
      v = new T(n);
      foreach (ref w; v) foreach (e; E) mixin("get(w."~e~");");
    }
  }

  const struct PutConf
  {
    bool newline = true, flush, exit;
    string floatFormat = "%.10f", delimiter = " ";
  }

  void put(alias conf = "{}", T...)(T v)
  {
    mixin("const PutConf c = "~conf~"; putMain!c(v);");
  }
  void putB(alias conf = "{}", S, T)(bool c, S t, T f)
  {
    if (c) put!conf(t);
    else put!conf(f);
  }
  void 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;
    }
    void get(T)(ref T v)
    {
      if (sp.empty) nextLine();
      v = sp.front.to!T;
      sp.popFront();
    }

    void putMain(PutConf c, T...)(T v)
    {
      foreach (i, w; v) {
        putOne!c(w);
        if (i+1 < v.length) OUT.write(c.delimiter);
      }
      static if (c.newline) OUT.writeln;
      static if (c.flush) OUT.flush();
      static if (c.exit) exit(0);
    }
    void putOne(PutConf c, T)(T v)
    {
      static if (isInputRange!T && !isSomeString!T) putRange!c(v);
      else static if (isFloatingPoint!T) OUT.write(format(c.floatFormat, v));
      else static if (hasMember!(T, "fprint")) v.fprint(OUT);
      else OUT.write(v);
    }
    void putRange(PutConf c, T)(T v)
    {
      auto w = v;
      while (!w.empty) {
        putOne!c(w.front); w.popFront();
        if (!w.empty) OUT.write(c.delimiter);
      }
    }
  }
}
0