uppga.c (1137B)
1 #include "common.h" 2 3 static void supporting(stack_u64 *s, stack_u64 *t, brick_t *bricks, size_t n) { 4 size_t i, j; 5 brick_t b; 6 7 for (i = 0; i < n; i++) { 8 if (bricks[i].ivs[2].lb > 1) { 9 b = bricks[i]; 10 gravitize(&b); 11 12 for (j = 0; j < n; j++) { 13 if (i != j && brick_nei(&b, &bricks[j])) { 14 stack_u64_push(s, i); 15 stack_u64_push(t, j); 16 } 17 } 18 } 19 } 20 } 21 22 int main(int argc, char **argv) { 23 size_t i; 24 char **lines; 25 size_t nlines = readlines(&lines, "input"); 26 27 brick_t bricks[nlines]; 28 read_bricks(bricks, lines, nlines); 29 sort_bricks(bricks, nlines); 30 gravitize_all(bricks, nlines); 31 32 stack_u64 s, t; 33 stack_u64_init(&s); 34 stack_u64_init(&t); 35 supporting(&s, &t, bricks, nlines); 36 37 uint64_t deg[nlines]; 38 memset(deg, 0, nlines * sizeof(*deg)); 39 for (i = 0; i < s.nmemb; i++) 40 deg[s.data[i]]++; 41 42 uint8_t unsafe[nlines]; 43 memset(unsafe, 0, nlines); 44 for (i = 0; i < s.nmemb; i++) 45 if (deg[s.data[i]] == 1) 46 unsafe[t.data[i]] = 1; 47 48 uint64_t count = 0; 49 for (i = 0; i < nlines; i++) 50 if (!unsafe[i]) 51 count++; 52 53 printf("%lld\n", count); 54 }