Source code for submission s1010

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. short nlp[15000];
  7. short neigh[11000][21000];
  8. char visited[15000];
  9. short 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. //printf("root %d\n", root);
  36. qreset();
  37. qpush(root);
  38. paws = 0;
  39. while (1) {
  40. node = qpop();
  41. if (node < 0) break;
  42. ispaw = 0;
  43. for (i=0; i<nlp[node]; i++) {
  44. ispaw += qpush(neigh[node][i]);
  45. }
  46. if (!ispaw) paws++;
  47. }
  48. if (paws >= 4) isbun = 1;
  49. }
  50. return isbun;
  51. }
  52.  
  53. int main(int argc, char **argv)
  54. {
  55. int rv, i, lines, p1, p2;
  56. while (1) {
  57. memset(nlp, 0, sizeof(nlp));
  58. memset(visited, 0, sizeof(visited));
  59. rv = scanf("%d%d", &points, &lines);
  60. if (rv != 2) break;
  61. for (i=0; i<lines; i++) {
  62. scanf("%d%d", &p1, &p2);
  63. neigh[p1][nlp[p1]++] = p2;
  64. neigh[p2][nlp[p2]++] = p1;
  65. }
  66. printf("%s\n", c() ? "YES" : "NO");
  67. }
  68. return 0;
  69. }
  70.  

Diff to submission s980

fn.c

--- c5.s980.cteam089.fn.c.0.fn.c
+++ c5.s1010.cteam089.fn.c.0.fn.c
@@ -4,8 +4,8 @@
 #include <math.h>
 
-int nlp[15000];
-int neigh[15000][25000];
-int visited[15000];
-int queue[25000];
+short nlp[15000];
+short neigh[11000][21000];
+char visited[15000];
+short queue[25000];
 int qstart, qend;
 int points;
@@ -33,4 +33,5 @@
         for (root=1; root<points+1; root++) {
                 if (visited[root]) continue;
+                //printf("root %d\n", root);
                 qreset();
                 qpush(root);