Source code for submission s999

Go to diff to previous submission

fn.cpp

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <vector>
  4. #include <map>
  5.  
  6. using namespace std;
  7.  
  8. typedef struct Node {
  9. 	int polygon;
  10. 	int connects;
  11. 	Node() : polygon(-1), connects(0) {}
  12. };
  13.  
  14. typedef std::vector<Node> Mappp;
  15.  
  16. Mappp mappp;
  17.  
  18. map<int, int> paws;
  19.  
  20. int main()
  21. {
  22. int n, m;
  23.  
  24. while (scanf("%d %d", &n, &m) == 2)
  25. {	
  26. 	mappp.clear();
  27. 	mappp.resize(n+1);
  28.  
  29. 	int i;
  30. 	for (i = 0; i < m; ++i) {
  31. 		int a, b;
  32. 		scanf("%d %d", &a, &b);
  33.  
  34. 		mappp[a].connects += 1;
  35. 		mappp[b].connects += 1;
  36.  
  37. 		if (mappp[a].polygon == -1 && mappp[b].polygon == -1) {
  38. 			mappp[b].polygon = a;
  39. 			mappp[a].polygon = a;
  40. 		}
  41.  
  42. 		if (mappp[a].polygon == -1) {
  43. 			mappp[a].polygon = mappp[b].polygon;
  44. 		}
  45.  
  46. 		if (mappp[b].polygon == -1) {
  47. 			mappp[b].polygon = mappp[a].polygon;
  48. 		}
  49.  
  50. 		if (mappp[b].polygon != mappp[a].polygon) {
  51. 			int oldPolygon = mappp[b].polygon;
  52.  
  53. 			for (Mappp::iterator it = mappp.begin(); it != mappp.end(); ++it) {
  54. 				if (it->polygon == oldPolygon)
  55. 					it->polygon = mappp[a].polygon;
  56. 			}
  57. 		}
  58. 	}
  59.  
  60. 	bool found = false;
  61.  
  62. 	paws.clear();
  63.  
  64. 	for (Mappp::iterator it = mappp.begin(); it != mappp.end(); ++it) {
  65. 		if (it->connects == 1)
  66. 			paws[it->polygon] += 1;
  67.  
  68. 		if (paws[it->polygon] >= 4) {
  69. 			found = true;
  70. 			break;
  71. 		}
  72. 	}
  73.  
  74. 	if (found)
  75. 		printf("YES\n");
  76. 	else
  77. 		printf("NO\n");
  78. }
  79.  
  80.  
  81.  
  82. return 0;
  83. }
  84.  

Diff to submission s856

fn.cpp

--- c5.s856.cteam076.fn.cpp.0.fn.cpp
+++ c5.s999.cteam076.fn.cpp.0.fn.cpp
@@ -1,10 +1,20 @@
 #include <stdio.h>
 #include <stdlib.h>
+#include <vector>
+#include <map>
 
 using namespace std;
 
-typedef int* Map;
+typedef struct Node {
+        int polygon;
+        int connects;
+        Node() : polygon(-1), connects(0) {}
+};
 
-Map map;
+typedef std::vector<Node> Mappp;
+
+Mappp mappp;
+
+map<int, int> paws;
 
 int main()
@@ -13,6 +23,7 @@
 
 while (scanf("%d %d", &n, &m) == 2)
-{
-        map = (Map)calloc(n+1, sizeof(int));
+{       
+        mappp.clear();
+        mappp.resize(n+1);
         
         int i;
@@ -21,23 +32,48 @@
                 scanf("%d %d", &a, &b);
                 
-                ++map[a];
-                ++map[b];
+                mappp[a].connects += 1;
+                mappp[b].connects += 1;
+                
+                if (mappp[a].polygon == -1 && mappp[b].polygon == -1) {
+                        mappp[b].polygon = a;
+                        mappp[a].polygon = a;
+                }
+                
+                if (mappp[a].polygon == -1) {
+                        mappp[a].polygon = mappp[b].polygon;
+                }
+                
+                if (mappp[b].polygon == -1) {
+                        mappp[b].polygon = mappp[a].polygon;
+                }
+                
+                if (mappp[b].polygon != mappp[a].polygon) {
+                        int oldPolygon = mappp[b].polygon;
+                        
+                        for (Mappp::iterator it = mappp.begin(); it != mappp.end(); ++it) {
+                                if (it->polygon == oldPolygon)
+                                        it->polygon = mappp[a].polygon;
+                        }
+                }
         }
 
-        int paws = 0;   
-        for (i = 1; i <= n; ++i) {
-                //printf("i%d: %d\n", i, map[i]);
-                if (map[i] == 1)
-                        ++paws;
-                if (paws >= 4)
+        bool found = false;
+        
+        paws.clear();
+        
+        for (Mappp::iterator it = mappp.begin(); it != mappp.end(); ++it) {
+                if (it->connects == 1)
+                        paws[it->polygon] += 1;
+                
+                if (paws[it->polygon] >= 4) {
+                        found = true;
                         break;
+                }
         }
         
-        if (paws >= 4)
+        if (found)
                 printf("YES\n");
         else
                 printf("NO\n");
-        
-        free(map);
 }