Source code for submission s980

Go to diff to previous submission

fn.c

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <math.h>
  5.  
  6. int nlp[15000];
  7. int neigh[15000][25000];
  8. int visited[15000];
  9. int queue[25000];
  10. int qstart, qend;
  11. int points;
  12.  
  13. void qreset() {
  14. qstart = 0;
  15. qend = 0;
  16. }
  17.  
  18. int qpush(int n) {
  19. if (visited[n]) return 0;
  20. visited[n] = 1;
  21. //printf("push %d @ %d\n", n, qend);
  22. queue[qend++] = n;
  23. return 1;
  24. }
  25.  
  26. int qpop() {
  27. if (qstart==qend) return -1;
  28. return queue[qstart++];
  29. }
  30.  
  31. int c() {
  32. int root, node, i, paws, ispaw, isbun=0;
  33. for (root=1; root<points+1; root++) {
  34. if (visited[root]) continue;
  35. qreset();
  36. qpush(root);
  37. paws = 0;
  38. while (1) {
  39. node = qpop();
  40. if (node < 0) break;
  41. ispaw = 0;
  42. for (i=0; i<nlp[node]; i++) {
  43. ispaw += qpush(neigh[node][i]);
  44. }
  45. if (!ispaw) paws++;
  46. }
  47. if (paws >= 4) isbun = 1;
  48. }
  49. return isbun;
  50. }
  51.  
  52. int main(int argc, char **argv)
  53. {
  54. int rv, i, lines, p1, p2;
  55. while (1) {
  56. memset(nlp, 0, sizeof(nlp));
  57. memset(visited, 0, sizeof(visited));
  58. rv = scanf("%d%d", &points, &lines);
  59. if (rv != 2) break;
  60. for (i=0; i<lines; i++) {
  61. scanf("%d%d", &p1, &p2);
  62. neigh[p1][nlp[p1]++] = p2;
  63. neigh[p2][nlp[p2]++] = p1;
  64. }
  65. printf("%s\n", c() ? "YES" : "NO");
  66. }
  67. return 0;
  68. }
  69.  

Diff to submission s450

fn.c

--- c5.s450.cteam089.fn.c.0.fn.c
+++ c5.s980.cteam089.fn.c.0.fn.c
@@ -4,23 +4,64 @@
 #include <math.h>
 
-int nlp[20000];
+int nlp[15000];
+int neigh[15000][25000];
+int visited[15000];
+int queue[25000];
+int qstart, qend;
+int points;
+
+void qreset() {
+        qstart = 0;
+        qend = 0;
+}
+
+int qpush(int n) {
+        if (visited[n]) return 0;
+        visited[n] = 1;
+        //printf("push %d @ %d\n", n, qend);
+        queue[qend++] = n;
+        return 1;
+}
+
+int qpop() {
+        if (qstart==qend) return -1;
+        return queue[qstart++];
+}
+
+int c() {
+        int root, node, i, paws, ispaw, isbun=0;
+        for (root=1; root<points+1; root++) {
+                if (visited[root]) continue;
+                qreset();
+                qpush(root);
+                paws = 0;
+                while (1) {
+                        node = qpop();
+                        if (node < 0) break;
+                        ispaw = 0;
+                        for (i=0; i<nlp[node]; i++) {
+                                ispaw += qpush(neigh[node][i]);
+                        }
+                        if (!ispaw) paws++;
+                }
+                if (paws >= 4) isbun = 1;
+        }
+        return isbun;
+}
 
 int main(int argc, char **argv)
 {
-        int rv, i, points, lines, p1, p2, bunny;
+        int rv, i, lines, p1, p2;
         while (1) {
-                memset(nlp, 0, 20000*sizeof(int));
+                memset(nlp, 0, sizeof(nlp));
+                memset(visited, 0, sizeof(visited));
                 rv = scanf("%d%d", &points, &lines);
                 if (rv != 2) break;
                 for (i=0; i<lines; i++) {
                         scanf("%d%d", &p1, &p2);
-                        nlp[p1]++;
-                        nlp[p2]++;
-                }
-                bunny = 0;
-                for (i=0; i<points; i++) {
-                        if (nlp[i] >= 4) bunny = 1;
+                        neigh[p1][nlp[p1]++] = p2;
+                        neigh[p2][nlp[p2]++] = p1;
                 }
-                printf("%s\n", bunny ? "YES" : "NO");
+                printf("%s\n", c() ? "YES" : "NO");
         }
         return 0;