Source code for submission s913

Go to diff to previous submission

fn.cpp

  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4.  
  5. struct Point {
  6. 	unsigned counter;
  7. 	vector<short> points;
  8.  
  9. 	Point() {
  10. 		counter = 0;
  11. 	}
  12. };
  13.  
  14. Point ** graph;
  15. unsigned N;
  16.  
  17. inline bool isPaw(unsigned point) {
  18. 	return (graph[point]->counter == 1);
  19. }
  20.  
  21. bool isBunny(unsigned point) {
  22. 	for(vector<short>::iterator it = graph[point]->points.begin(); it != graph[point]->points.end(); ++it) {
  23. 		if(!isPaw(*it))
  24. 			return false;
  25. 	}
  26. 	return true;
  27. }
  28.  
  29. int main() {
  30. 	unsigned points;
  31. 	unsigned lines;
  32. 	while(cin >> points >> lines) {
  33. 		graph = new Point * [points];
  34. 		for (unsigned i = 0; i < points; i++) {
  35. 			graph[i] = new Point();
  36. 		}
  37.  
  38. 		for (unsigned i = 0; i < lines; i++) {
  39. 			unsigned x, y;
  40. 			cin >> x >> y;
  41. 			graph[x-1]->points.push_back(y-1);
  42. 			graph[y-1]->points.push_back(x-1);
  43. 			graph[x-1]->counter++;
  44. 			graph[y-1]->counter++;
  45. 		}
  46.  
  47. 		N = points;		
  48.  
  49. 		bool found = false;
  50. 		for (unsigned i = 0; i < N; i++) {
  51. 			if(graph[i]->counter == 4 && isBunny(i)) {
  52. 				cout << "YES" << endl;
  53. 				found = true;
  54. 				break;
  55. 			}
  56. 		}
  57.  
  58. 		if (!found)
  59. 			cout << "NO" << endl;
  60.  
  61. 		for (unsigned i = 0; i < points; i++) {
  62. 			delete graph[i];
  63. 		}
  64. 		delete [] graph;
  65. 	}
  66.  
  67. 	return 0;
  68. }
  69.  
  70.  
  71.  
  72.  

Diff to submission s867

fn.cpp

--- 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;