Source code for submission s767

Go to diff to previous submission

fr.c

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <math.h>
  5.  
  6. int conn[2000][2000];
  7. int pipes[2000];
  8. int nodes;
  9.  
  10. int count(int node, int from) {
  11. 	int i, inputc= 1000000000, childc = 0;
  12. 	//printf("count node %d from %d\n", node, from);
  13. 	if (pipes[node]==1 && from != -1) {
  14. 		//printf("leaf %d\n", node);
  15. 		return conn[node][from];
  16. 	}
  17. 	for (i=1; i<nodes+1; i++) {
  18. 		if (i==from) {
  19. 			inputc = conn[node][i];
  20. 		} else {
  21. 			//childc += conn[node][i];
  22. 			if (conn[node][i] > 0) childc += count(i, node);
  23. 		}
  24. 	}
  25. 	//printf("node %d from %d input %d child %d\n", node, from, inputc, childc);
  26. 	if (childc == 0) return inputc;
  27. 	return childc > inputc ? inputc : childc;
  28. }
  29.  
  30. int main(int argc, char **argv)
  31. {
  32. 	int rv, root, i, n1, n2, w;
  33. 	while (1) {
  34. 		rv = scanf("%d%d", &nodes, &root);
  35. 		if (rv != 2) break;
  36. 		memset(conn, 0, sizeof(conn));
  37. 		memset(pipes, 0, sizeof(pipes));
  38. 		for (i=0; i<nodes-1; i++) {
  39. 			scanf("%d%d%d", &n1, &n2, &w);
  40. 			conn[n1][n2] = w;
  41. 			conn[n2][n1] = w;
  42. 			pipes[n1]++;
  43. 			pipes[n2]++;
  44. 		}
  45. 		printf("%d\n", count(root, -1));
  46. 	}
  47. 	return 0;
  48. }
  49.  

Diff to submission s708

fr.c

--- c5.s708.cteam089.fr.c.0.fr.c
+++ c5.s767.cteam089.fr.c.0.fr.c
@@ -5,4 +5,5 @@
 
 int conn[2000][2000];
+int pipes[2000];
 int nodes;
 
@@ -10,4 +11,8 @@
         int i, inputc= 1000000000, childc = 0;
         //printf("count node %d from %d\n", node, from);
+        if (pipes[node]==1 && from != -1) {
+                //printf("leaf %d\n", node);
+                return conn[node][from];
+        }
         for (i=1; i<nodes+1; i++) {
                 if (i==from) {
@@ -30,8 +35,11 @@
                 if (rv != 2) break;
                 memset(conn, 0, sizeof(conn));
+                memset(pipes, 0, sizeof(pipes));
                 for (i=0; i<nodes-1; i++) {
                         scanf("%d%d%d", &n1, &n2, &w);
                         conn[n1][n2] = w;
                         conn[n2][n1] = w;
+                        pipes[n1]++;
+                        pipes[n2]++;
                 }
                 printf("%d\n", count(root, -1));