Go to diff to previous submission
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> 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, lines, p1, p2; while (1) { if (rv != 2) break; for (i=0; i<lines; i++) { neigh[p1][nlp[p1]++] = p2; neigh[p2][nlp[p2]++] = p1; } } return 0; }
--- 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;