Source code for submission s867

Go to diff to previous submission

fn.cpp

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

Diff to submission s832

fn.cpp

--- c5.s832.cteam009.fn.cpp.0.fn.cpp
+++ c5.s867.cteam009.fn.cpp.0.fn.cpp
@@ -2,28 +2,10 @@
 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;
-        }
+inline bool isPaw(unsigned point) {
+        return (connections[point] == 1);
 }
 
@@ -57,8 +39,4 @@
                         }
                 }
-                
-                paws = new short [points];
-                for (unsigned i = 0; i < points; i++)
-                        paws[i] = -1;           
 
                 connections = new unsigned [points];
@@ -89,5 +67,4 @@
                         cout << "NO" << endl;
 
-                delete [] paws;
                 delete [] connections;