Go to diff to previous submission
#include<iostream> using namespace std; short * paws; bool ** graph; unsigned * connections; unsigned N; bool isPaw(unsigned point) { if(paws[point] != -1) return (bool) paws[point]; else { bool con = false; for(unsigned i = 0; i < N; i++) { if(graph[point][i] == 1) { if (con) { paws[point] = 0; return false; } else { con = true; } } } paws[point] = 1; return true; } } bool isBunny(unsigned point) { short paws = 0; for(unsigned i = 0; i < N; i++) { if(graph[point][i] == 1) { if(isPaw(graph[point][i])) { if(++paws > 4) { return false; } } } } if (paws == 4) return true; else return false; } int main() { unsigned points; unsigned lines; while(cin >> points >> lines) { graph = new bool * [points]; for (unsigned i = 0; i < points; i++) { graph[i] = new bool [points]; for (unsigned j = 0; j < points; j++) { graph[i][j] = false; } } paws = new short [points]; for (unsigned i = 0; i < points; i++) paws[i] = -1; connections = new unsigned [points]; for (unsigned i = 0; i < points; i++) connections[i] = 0; for (unsigned i = 0; i < lines; i++) { unsigned x, y; cin >> x >> y; graph[x-1][y-1] = true; graph[y-1][x-1] = true; connections[x-1]++; connections[y-1]++; } N = points; bool found = false; for (unsigned i = 0; i < N; i++) { if(connections[i] == 4 && isBunny(i)) { cout << "YES" << endl; found = true; break; } } if (!found) cout << "NO" << endl; delete [] paws; delete [] connections; for (unsigned i = 0; i < points; i++) { delete [] graph[i]; } delete [] graph; } return 0; }
--- c5.s801.cteam009.fn.cpp.0.fn.cpp +++ c5.s832.cteam009.fn.cpp.0.fn.cpp @@ -4,4 +4,5 @@ short * paws; bool ** graph; +unsigned * connections; unsigned N; @@ -31,6 +32,8 @@ for(unsigned i = 0; i < N; i++) { if(graph[point][i] == 1) { - if(++paws > 4) { - return false; + if(isPaw(graph[point][i])) { + if(++paws > 4) { + return false; + } } } @@ -60,4 +62,8 @@ paws[i] = -1; + connections = new unsigned [points]; + for (unsigned i = 0; i < points; i++) + connections[i] = 0; + for (unsigned i = 0; i < lines; i++) { unsigned x, y; @@ -65,4 +71,6 @@ graph[x-1][y-1] = true; graph[y-1][x-1] = true; + connections[x-1]++; + connections[y-1]++; } @@ -71,5 +79,5 @@ bool found = false; for (unsigned i = 0; i < N; i++) { - if(isBunny(i)) { + if(connections[i] == 4 && isBunny(i)) { cout << "YES" << endl; found = true; @@ -82,4 +90,5 @@ delete [] paws; + delete [] connections; for (unsigned i = 0; i < points; i++) {