Source code for submission s677

Go to diff to previous submission

fn.cpp

  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4.  
  5. #include<cmath>
  6. #include<cctype>
  7. #include<climits>
  8. #include<algorithm>
  9. #include<utility>
  10. #include<string>
  11.  
  12. #include<deque>
  13. #include<list>
  14. #include<map>
  15. #include<queue>
  16. #include<set>
  17. #include<stack>
  18. #include<vector>
  19.  
  20.  
  21. using namespace std;
  22.  
  23. #define REP(i,N) for (int i = 0; i < (N); i++)
  24. #define FOR(i,a,b) for (int i = (a); i <= (b); i++)
  25. #define FORI(i,a,b) for (int i = (a); i < (b); i++)
  26. #define FORD(i,a,b) for (int i = (a)-1; i >= (b); i--)
  27. #define DP(arg...) fprintf(stderr, ## arg)
  28.  
  29. typedef long long ll;
  30. typedef long double ld;
  31. typedef pair<int,int> ii;
  32.  
  33. int N,M;
  34. vector<int> E[11000];
  35. int deg[11000];
  36. int vis[11000];
  37. int d3, d4; int psm, ps3;
  38. int sm[11000], s3[11000];
  39. int cn;
  40. vector<int> vee;
  41. void dfs(int v) {
  42. 	//DP("%d ", v);
  43. 		cn++;
  44. 		if (deg[v] >= 3) d3++;
  45. 		if (deg[v] >= 4) d4++;
  46. 		if (deg[v] == 3) vee.push_back(v);
  47. 		vis[v] = 1;
  48. 		REP(i,E[v].size()) {
  49. 			if (deg[v] == 3 && sm[E[v][i]] == 0) {
  50. 				sm[E[v][i]] = 1;
  51. 				psm++;
  52. 			}
  53. 			if (deg[v] == 3 && deg[E[v][i]] == 3 && s3[E[v][i]] == 0) {
  54. 					s3[E[v][i]] = 1;
  55. 					ps3++;
  56. 			}
  57. 			if (!vis[E[v][i]])
  58. 				dfs(E[v][i]);
  59. 		}
  60. }
  61.  
  62. void solve() {
  63. 	REP(i,N) { deg[i] = 0; E[i].clear(); vis[i] = 0; sm[i] = 0; s3[i] = 0; }
  64. 	REP(i,M) { int a,b;
  65. 			scanf("%d%d", &a, &b);
  66. 			a--; b--;
  67. 			deg[a]++; deg[b]++;
  68. 			E[a].push_back(b);
  69. 			E[b].push_back(a);
  70.  
  71. 	}
  72.  
  73. 	REP(k,N) {
  74. 				d3 = 0, d4 = 0;
  75. 				psm = 0, ps3 = 0;
  76. 				cn = 0;
  77.  
  78. 				vee.clear();
  79. 				if (!vis[k]) dfs(k);
  80. 				else continue;
  81. 				//DP("%d\n", d3);
  82. 				if (d4 >= 1) { printf("YES\n"); return; }
  83. 				if (d3 >= 5) { printf("YES\n"); return; }
  84. 				if (d3 == 4 && cn > 4) { printf("YES\n"); return; }
  85. 				if (d3 == 3) {
  86. 						int tmp = 0;
  87. 						REP(t,3) {
  88. 							REP(ss,3) {
  89. 									if (deg[E[vee[t]][ss]] == 3) tmp++;
  90. 							}
  91. 						}
  92. 						if (tmp != 6)
  93. 							{ printf("YES\n"); return; }
  94. 				}
  95. 				if (d3 == 2) {
  96. 						//DP("%d %d\n", ps3, psm);
  97. 						if (ps3 == 2) {
  98. 								if (psm >= 6)
  99. 									{ printf("YES\n"); return; }
  100. 						}
  101. 						else {
  102. 							int spol = 0;
  103. 							int myv = vee[0];
  104. 							REP(t,3) {
  105. 								int sous = E[myv][t];
  106. 								int tmp = 0;
  107. 								REP(hr,E[sous].size()) {
  108. 									if (deg[E[sous][hr]] == 3) tmp++;
  109. 								}
  110. 								if (tmp == 2) spol++;
  111. 							}
  112. 							if (spol < 2) {
  113. 								printf("YES\n"); return;
  114. 							}							
  115. 						}
  116.  
  117. 				}
  118. 	}
  119. 	printf("NO\n");
  120.  
  121. }
  122.  
  123. int main() {
  124. 	while (scanf("%d%d", &N, &M) != EOF) {
  125. 		solve();
  126. 	}
  127. 	return 0;
  128. }
  129.  

Diff to submission s516

fn.cpp

--- c5.s516.cteam022.fn.cpp.0.fn.cpp
+++ c5.s677.cteam022.fn.cpp.0.fn.cpp
@@ -35,12 +35,24 @@
 int deg[11000];
 int vis[11000];
-int d3, d4;
-
+int d3, d4; int psm, ps3;
+int sm[11000], s3[11000];
+int cn;
+vector<int> vee;
 void dfs(int v) {
         //DP("%d ", v);
+                cn++;
                 if (deg[v] >= 3) d3++;
                 if (deg[v] >= 4) d4++;
+                if (deg[v] == 3) vee.push_back(v);
                 vis[v] = 1;
                 REP(i,E[v].size()) {
+                        if (deg[v] == 3 && sm[E[v][i]] == 0) {
+                                sm[E[v][i]] = 1;
+                                psm++;
+                        }
+                        if (deg[v] == 3 && deg[E[v][i]] == 3 && s3[E[v][i]] == 0) {
+                                        s3[E[v][i]] = 1;
+                                        ps3++;
+                        }
                         if (!vis[E[v][i]])
                                 dfs(E[v][i]);
@@ -49,5 +61,5 @@
 
 void solve() {
-        REP(i,N) { deg[i] = 0; E[i].clear(); vis[i] = 0; }
+        REP(i,N) { deg[i] = 0; E[i].clear(); vis[i] = 0; sm[i] = 0; s3[i] = 0; }
         REP(i,M) { int a,b;
                         scanf("%d%d", &a, &b);
@@ -58,8 +70,50 @@
                         
         }
+        
         REP(k,N) {
                                 d3 = 0, d4 = 0;
+                                psm = 0, ps3 = 0;
+                                cn = 0;
+                                
+                                vee.clear();
                                 if (!vis[k]) dfs(k);
-                                if (d3 >= 2 || d4 >= 1) { printf("YES\n"); return; }
+                                else continue;
+                                //DP("%d\n", d3);
+                                if (d4 >= 1) { printf("YES\n"); return; }
+                                if (d3 >= 5) { printf("YES\n"); return; }
+                                if (d3 == 4 && cn > 4) { printf("YES\n"); return; }
+                                if (d3 == 3) {
+                                                int tmp = 0;
+                                                REP(t,3) {
+                                                        REP(ss,3) {
+                                                                        if (deg[E[vee[t]][ss]] == 3) tmp++;
+                                                        }
+                                                }
+                                                if (tmp != 6)
+                                                        { printf("YES\n"); return; }
+                                }
+                                if (d3 == 2) {
+                                                //DP("%d %d\n", ps3, psm);
+                                                if (ps3 == 2) {
+                                                                if (psm >= 6)
+                                                                        { printf("YES\n"); return; }
+                                                }
+                                                else {
+                                                        int spol = 0;
+                                                        int myv = vee[0];
+                                                        REP(t,3) {
+                                                                int sous = E[myv][t];
+                                                                int tmp = 0;
+                                                                REP(hr,E[sous].size()) {
+                                                                        if (deg[E[sous][hr]] == 3) tmp++;
+                                                                }
+                                                                if (tmp == 2) spol++;
+                                                        }
+                                                        if (spol < 2) {
+                                                                printf("YES\n"); return;
+                                                        }                                                       
+                                                }
+                                                
+                                }
         }
         printf("NO\n");