Source code for submission s832

Go to diff to previous submission

fn.cpp

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

Diff to submission s801

fn.cpp

--- 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++) {