uppga.c (2071B)
1 #include "common.h" 2 3 #define ASIZE 26 4 5 static inline size_t idx(char *s) { 6 size_t a = (size_t)(s[0] - 'a'); 7 size_t b = (size_t)(s[1] - 'a'); 8 size_t c = (size_t)(s[2] - 'a'); 9 10 return (a * ASIZE * ASIZE) + (b * ASIZE) + c; 11 } 12 13 static void graph_setup(graph_t *g, char **lines, size_t nlines) { 14 char *cp; 15 size_t c = 0; 16 size_t i; 17 size_t dict[ASIZE * ASIZE * ASIZE]; 18 for (i = 0; i < ASIZE * ASIZE * ASIZE; i++) 19 dict[i] = SIZE_MAX; 20 21 for (i = 0; i < nlines; i++) { 22 cp = lines[i]; 23 while (*cp != '\0' && *cp != '\n') { 24 if ('a' <= *cp && *cp <= 'z') { 25 if (dict[idx(cp)] == UINT64_MAX) { 26 dict[idx(cp)] = c; 27 c++; 28 } 29 cp += 3; 30 } else { 31 cp++; 32 } 33 } 34 } 35 36 graph_init(g, c); 37 38 size_t cnode; 39 for (i = 0; i < nlines; i++) { 40 cp = lines[i]; 41 cnode = idx(cp); 42 cp += 4; 43 while (*cp != '\0' && *cp != '\n') { 44 if ('a' <= *cp && *cp <= 'z') { 45 graph_add_edge(g, dict[cnode], dict[idx(cp)]); 46 cp += 3; 47 } else { 48 cp++; 49 } 50 } 51 } 52 } 53 54 static uint64_t partition_wrapper(graph_t *g) { 55 size_t i, j; 56 igraph_t h; 57 igraph_vector_int_t partition, partition2, cut; 58 igraph_real_t value; 59 60 igraph_empty(&h, g->n, IGRAPH_UNDIRECTED); 61 62 for (i = 0; i < g->n; i++) { 63 for (j = 0; j < (g->nbrs[i]).nmemb; j++) { 64 igraph_add_edge(&h, i, (g->nbrs[i]).data[j]); 65 } 66 } 67 68 igraph_vector_int_init(&partition, 0); 69 igraph_vector_int_init(&partition2, 0); 70 igraph_vector_int_init(&cut, 0); 71 72 igraph_mincut(&h, &value, &partition, &partition2, &cut, NULL); 73 74 size_t p1s = igraph_vector_int_size(&partition); 75 size_t p2s = igraph_vector_int_size(&partition2); 76 77 igraph_vector_int_destroy(&cut); 78 igraph_vector_int_destroy(&partition2); 79 igraph_vector_int_destroy(&partition); 80 igraph_destroy(&h); 81 82 return p1s * p2s; 83 } 84 85 int main(int argc, char **argv) { 86 char **lines; 87 size_t nlines = readlines(&lines, "input"); 88 89 graph_t g; 90 graph_setup(&g, lines, nlines); 91 92 uint64_t prod = partition_wrapper(&g); 93 printf("%llu\n", prod); 94 }