#328354 (C) No.421 しろくろチョコレート

提出ソース

結果

問題	No.421 しろくろチョコレート
ユーザー	akakimidori
提出日時	2019-03-23 16:52:48
言語	C (gcc 12.3.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	4,319 bytes
コンパイル時間	965 ms
コンパイル使用メモリ	32,028 KB
実行使用メモリ	4,348 KB
最終ジャッジ日時	2023-10-24 14:57:40
合計ジャッジ時間	2,489 ms
ジャッジサーバーID （参考情報）	judge12 / judge11

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,348 KB
testcase_01	AC	1 ms 4,348 KB
testcase_02	AC	1 ms 4,348 KB
testcase_03	AC	1 ms 4,348 KB
testcase_04	AC	1 ms 4,348 KB
testcase_05	AC	1 ms 4,348 KB
testcase_06	AC	1 ms 4,348 KB
testcase_07	AC	1 ms 4,348 KB
testcase_08	AC	1 ms 4,348 KB
testcase_09	AC	1 ms 4,348 KB
testcase_10	AC	1 ms 4,348 KB
testcase_11	AC	1 ms 4,348 KB
testcase_12	AC	1 ms 4,348 KB
testcase_13	AC	1 ms 4,348 KB
testcase_14	AC	1 ms 4,348 KB
testcase_15	AC	1 ms 4,348 KB
testcase_16	AC	2 ms 4,348 KB
testcase_17	AC	2 ms 4,348 KB
testcase_18	AC	1 ms 4,348 KB
testcase_19	AC	1 ms 4,348 KB
testcase_20	AC	1 ms 4,348 KB
testcase_21	AC	2 ms 4,348 KB
testcase_22	AC	1 ms 4,348 KB
testcase_23	AC	1 ms 4,348 KB
testcase_24	AC	1 ms 4,348 KB
testcase_25	AC	1 ms 4,348 KB
testcase_26	AC	1 ms 4,348 KB
testcase_27	AC	1 ms 4,348 KB
testcase_28	AC	1 ms 4,348 KB
testcase_29	AC	1 ms 4,348 KB
testcase_30	AC	1 ms 4,348 KB
testcase_31	AC	1 ms 4,348 KB
testcase_32	AC	1 ms 4,348 KB
testcase_33	AC	2 ms 4,348 KB
testcase_34	AC	1 ms 4,348 KB
testcase_35	AC	1 ms 4,348 KB
testcase_36	AC	1 ms 4,348 KB
testcase_37	AC	1 ms 4,348 KB
testcase_38	AC	2 ms 4,348 KB
testcase_39	AC	1 ms 4,348 KB
testcase_40	AC	1 ms 4,348 KB
testcase_41	AC	1 ms 4,348 KB
testcase_42	AC	1 ms 4,348 KB
testcase_43	AC	1 ms 4,348 KB
testcase_44	AC	1 ms 4,348 KB
testcase_45	AC	1 ms 4,348 KB
testcase_46	AC	1 ms 4,348 KB
testcase_47	AC	1 ms 4,348 KB
testcase_48	AC	1 ms 4,348 KB
testcase_49	AC	1 ms 4,348 KB
testcase_50	AC	1 ms 4,348 KB
testcase_51	AC	2 ms 4,348 KB
testcase_52	AC	1 ms 4,348 KB
testcase_53	AC	1 ms 4,348 KB
testcase_54	AC	1 ms 4,348 KB
testcase_55	AC	1 ms 4,348 KB
testcase_56	AC	1 ms 4,348 KB
testcase_57	AC	1 ms 4,348 KB
testcase_58	AC	1 ms 4,348 KB
testcase_59	AC	1 ms 4,348 KB
testcase_60	AC	2 ms 4,348 KB
testcase_61	AC	2 ms 4,348 KB
testcase_62	AC	1 ms 4,348 KB
testcase_63	AC	1 ms 4,348 KB
testcase_64	AC	1 ms 4,348 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>
#include<string.h>

typedef int32_t flow_type;

const flow_type flow_inf = 50 * 50 / 2;

typedef struct flow_edge {
  int32_t vertex;
  int32_t next;
  flow_type capacity;
} flow_edge;

typedef struct maxFlowGraph {
  flow_edge *edge;
  int32_t *start;
  int32_t vertex_num;
  int32_t pointer;
  int32_t edge_length;
} graph;

graph* new_graph (const int32_t vertex_num) {
  graph *g = (graph *) calloc (1, sizeof (graph));
  g->vertex_num = vertex_num;
  const int32_t initial_length = 4;
  g->edge = (flow_edge *) calloc (initial_length, sizeof (flow_edge));
  g->start = (int32_t *) calloc (vertex_num, sizeof (int32_t));
  g->pointer = 0;
  g->edge_length = initial_length;
  for (int32_t i = 0; i < vertex_num; ++i) {
    g->start[i] = -1;
  }
  return g;
}

void free_graph (graph * const g) {
  free (g->edge);
  free (g->start);
  free (g);
}

void add_edge (graph * const g, const int32_t from, const int32_t to, const flow_type capa) {
  if (g->pointer == g->edge_length) {
    g->edge_length *= 2;
    g->edge = (flow_edge *) realloc (g->edge, sizeof (flow_edge) * g->edge_length);
  }
  const int32_t p = g->pointer;
  g->edge[p] = (flow_edge) {to, g->start[from], capa};
  g->start[from] = p;
  g->edge[p + 1] = (flow_edge) {from, g->start[to], 0};
  g->start[to] = p + 1;
  g->pointer += 2;
}

flow_type dinic_dfs (const int32_t v, graph * const g, const int32_t dst, const int32_t * const level, int32_t * const iter, flow_type e) {
  if (v == dst) return e;
  flow_type sum = 0;
  for (int32_t p = iter[v]; p != -1; p = g->edge[p].next, iter[v] = p) {
    const int32_t u = g->edge[p].vertex;
    const flow_type capa = g->edge[p].capacity;
    if (level[u] <= level[v] || capa <= 0) continue;
    const flow_type f = dinic_dfs (u, g, dst, level, iter, capa < e ? capa : e);
    if (f > 0) {
      g->edge[p].capacity -= f;
      g->edge[p ^ 1].capacity += f;
      sum += f;
      e -= f;
      if (e <= 0) return sum;
    }
  }
  return sum;
}

flow_type dinic (graph * const g, const int32_t src, const int32_t dst) {
  const int32_t vertex_num = g->vertex_num;
  int32_t * const level = (int32_t *) calloc (vertex_num, sizeof (int32_t));
  int32_t * const queue = (int32_t *) calloc (vertex_num, sizeof (int32_t));
  int32_t * const iter  = (int32_t *) calloc (vertex_num, sizeof (int32_t));
  flow_type flow = 0;
  while (1) {
    memset (level, 0, sizeof (int32_t) * vertex_num);
    int32_t front = 0;
    int32_t last = 0;
    level[dst] = vertex_num;
    queue[last++] = dst;
    while (front < last && level[src] == 0) {
      const int32_t v = queue[front++];
      for (int32_t p = g->start[v]; p!=-1; p = g->edge[p].next) {
        const int32_t u = g->edge[p].vertex;
        if (g->edge[p ^ 1].capacity > 0 && level[u] == 0) {
          level[u] = level[v] - 1;
          queue[last++] = u;
	}
      }
    }
    if (level[src] == 0) break;
    memcpy (iter, g->start, sizeof (int32_t) * vertex_num);
    while (1) {
      flow_type f = dinic_dfs (src, g, dst, level, iter, flow_inf);
      if (f <= 0) break;
      flow += f;
    }
  }
  free (level);
  free (queue);
  free (iter);
  return flow;
}

typedef int32_t i32;

void run (void) {
  i32 n, m;
  scanf ("%" SCNi32 "%" SCNi32, &n, &m);
  char *s = (char *) calloc (n * m + 1, sizeof (char));
  for (i32 i = 0; i < n; ++i) {
    scanf ("%s", s + i * m);
  }
  graph *g = new_graph (n * m + 2);
  const i32 src = n * m;
  const i32 dst = n * m + 1;
  i32 cnt[2] = {0, 0};
  for (i32 i = 0; i < n; ++i) {
    for (i32 j = 0; j < m; ++j) {
      if (s[i * m + j] == '.') continue;
      cnt[(i + j) & 1]++;
      const i32 v = i * m + j;
      if ((i + j) & 1) {
        add_edge (g, v, dst, 1); 
        continue;
      }
      add_edge (g, src, v, 1);
      i32 d[] = {-1, 0, 1, 0};
      for (i32 k = 0; k < 4; ++k) {
        i32 x = i + d[k];
        i32 y = j + d[k ^ 1];
        if (0 <= x && x < n && 0 <= y && y < m && s[x * m + y] != '.') {
          add_edge (g, v, x * m + y, 1);
        }
      }
    }
  }
  i32 a = dinic (g, src, dst);
  i32 b = -a + (cnt[0] < cnt[1] ? cnt[0] : cnt[1]);
  i32 c = cnt[0] + cnt[1] - 2 * a - 2 * b;
  i32 ans = 100 * a + 10 * b + c;
  printf ("%" PRIi32 "\n", ans);
}

int main (void) {
  run ();
  return 0;
}

yukicoder

結果

テストケース

ソースコード