Go to diff to previous submission
#include<iostream> #include<vector> using namespace std; struct Point { unsigned counter; vector<short> points; Point() { counter = 0; } }; Point ** graph; unsigned N; inline bool isPaw(unsigned point) { return (graph[point]->counter == 1); } bool isBunny(unsigned point) { for(vector<short>::iterator it = graph[point]->points.begin(); it != graph[point]->points.end(); ++it) { if(!isPaw(*it)) return false; } return true; } int main() { unsigned points; unsigned lines; while(cin >> points >> lines) { graph = new Point * [points]; for (unsigned i = 0; i < points; i++) { graph[i] = new Point(); } for (unsigned i = 0; i < lines; i++) { unsigned x, y; cin >> x >> y; graph[x-1]->points.push_back(y-1); graph[y-1]->points.push_back(x-1); graph[x-1]->counter++; graph[y-1]->counter++; } N = points; bool found = false; for (unsigned i = 0; i < N; i++) { if(graph[i]->counter == 4 && isBunny(i)) { cout << "YES" << endl; found = true; break; } } if (!found) cout << "NO" << endl; for (unsigned i = 0; i < points; i++) { delete graph[i]; } delete [] graph; } return 0; }
--- c5.s867.cteam009.fn.cpp.0.fn.cpp +++ c5.s913.cteam009.fn.cpp.0.fn.cpp @@ -1,29 +1,28 @@ #include<iostream> +#include<vector> using namespace std; -bool ** graph; -unsigned * connections; +struct Point { + unsigned counter; + vector<short> points; + + Point() { + counter = 0; + } +}; + +Point ** graph; unsigned N; inline bool isPaw(unsigned point) { - return (connections[point] == 1); + return (graph[point]->counter == 1); } 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; - } - } - } + for(vector<short>::iterator it = graph[point]->points.begin(); it != graph[point]->points.end(); ++it) { + if(!isPaw(*it)) + return false; } - - if (paws == 4) - return true; - else - return false; + return true; } @@ -32,23 +31,16 @@ unsigned lines; while(cin >> points >> lines) { - graph = new bool * [points]; + graph = new Point * [points]; for (unsigned i = 0; i < points; i++) { - graph[i] = new bool [points]; - for (unsigned j = 0; j < points; j++) { - graph[i][j] = false; - } + graph[i] = new Point(); } - 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]++; + graph[x-1]->points.push_back(y-1); + graph[y-1]->points.push_back(x-1); + graph[x-1]->counter++; + graph[y-1]->counter++; } @@ -57,5 +49,5 @@ bool found = false; for (unsigned i = 0; i < N; i++) { - if(connections[i] == 4 && isBunny(i)) { + if(graph[i]->counter == 4 && isBunny(i)) { cout << "YES" << endl; found = true; @@ -67,8 +59,6 @@ cout << "NO" << endl; - delete [] connections; - for (unsigned i = 0; i < points; i++) { - delete [] graph[i]; + delete graph[i]; } delete [] graph;