Source code for submission s890

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. int children[2000][2000];
  10. int childcount[2000];
  11.  
  12. int count(int node, int from) {
  13. 	int ii, i, inputc= 1000000000, childc = 0;
  14. 	//printf("count node %d from %d\n", node, from);
  15. 	if (pipes[node]==1 && from != -1) {
  16. 		//printf("leaf %d\n", node);
  17. 		return conn[node][from];
  18. 	}
  19. //	for (i=1; i<nodes+1; i++) {
  20. 	for (ii=0; ii<childcount[node]; ii++) {
  21. 		i = children[node][ii];
  22. 		if (i==from) {
  23. 			inputc = conn[node][i];
  24. 		} else {
  25. 			//childc += conn[node][i];
  26. 			if (conn[node][i] > 0) childc += count(i, node);
  27. 		}
  28. 	}
  29. 	//printf("node %d from %d input %d child %d\n", node, from, inputc, childc);
  30. 	if (childc == 0) return inputc;
  31. 	return childc > inputc ? inputc : childc;
  32. }
  33.  
  34. void addchild(int n1, int n2)
  35. {
  36. 	children[n1][childcount[n1]++] = n2;
  37. 	children[n2][childcount[n2]++] = n1;
  38. }
  39.  
  40. int main(int argc, char **argv)
  41. {
  42. 	int rv, root, i, n1, n2, w;
  43. 	while (1) {
  44. 		rv = scanf("%d%d", &nodes, &root);
  45. 		if (rv != 2) break;
  46. 		memset(conn, 0, sizeof(conn));
  47. 		memset(pipes, 0, sizeof(pipes));
  48. 		memset(childcount, 0, sizeof(childcount));
  49. 		for (i=0; i<nodes-1; i++) {
  50. 			scanf("%d%d%d", &n1, &n2, &w);
  51. 			conn[n1][n2] = w;
  52. 			conn[n2][n1] = w;
  53. 			pipes[n1]++;
  54. 			pipes[n2]++;
  55. 			addchild(n1, n2);
  56. 		}
  57. 		printf("%d\n", count(root, -1));
  58. 	}
  59. 	return 0;
  60. }
  61.  

Diff to submission s880

fr.c

--- c5.s880.cteam089.fr.c.0.fr.c
+++ c5.s890.cteam089.fr.c.0.fr.c
@@ -7,7 +7,9 @@
 int pipes[2000];
 int nodes;
+int children[2000][2000];
+int childcount[2000];
 
 int count(int node, int from) {
-        int i, inputc= 1000000000, childc = 0;
+        int ii, i, inputc= 1000000000, childc = 0;
         //printf("count node %d from %d\n", node, from);
         if (pipes[node]==1 && from != -1) {
@@ -15,5 +17,7 @@
                 return conn[node][from];
         }
-        for (i=1; i<nodes+1; i++) {
+//      for (i=1; i<nodes+1; i++) {
+        for (ii=0; ii<childcount[node]; ii++) {
+                i = children[node][ii];
                 if (i==from) {
                         inputc = conn[node][i];
@@ -28,4 +32,10 @@
 }
 
+void addchild(int n1, int n2)
+{
+        children[n1][childcount[n1]++] = n2;
+        children[n2][childcount[n2]++] = n1;
+}
+
 int main(int argc, char **argv)
 {
@@ -36,4 +46,5 @@
                 memset(conn, 0, sizeof(conn));
                 memset(pipes, 0, sizeof(pipes));
+                memset(childcount, 0, sizeof(childcount));
                 for (i=0; i<nodes-1; i++) {
                         scanf("%d%d%d", &n1, &n2, &w);
@@ -42,4 +53,5 @@
                         pipes[n1]++;
                         pipes[n2]++;
+                        addchild(n1, n2);
                 }
                 printf("%d\n", count(root, -1));