Source code for submission s1098

Go to diff to previous submission

fn.cpp

  1. //
  2. // File: fn.cc
  3. // Author: cteam030
  4. //
  5. // Created on October 19, 2013, 2:30 PM
  6. //
  7.  
  8. #include <stdlib.h>
  9. #include <iostream>
  10. #include <string>
  11. #include <vector>
  12.  
  13. using namespace std;
  14.  
  15. //
  16. //
  17. //
  18.  
  19. vector<vector<bool> > banned_pts;
  20.  
  21. bool routeFound(int pt1, int pt2, vector<int> next_pts[]);
  22.  
  23. int main(int argc, char** argv) {
  24.  
  25. int pts, lns;
  26. while(cin >> pts >> lns) {
  27. vector<int> next_pts[pts+1];
  28. bool found = false;
  29. for(int i = 0; i < lns; i++) {
  30. int pt1,pt2;
  31. cin >> pt1 >> pt2;
  32. next_pts[pt1].push_back(pt2);
  33. next_pts[pt2].push_back(pt1);
  34. if(next_pts[pt1].size()>=4 || next_pts[pt2].size() >= 4)
  35. found = true;
  36. }
  37. if(found) {
  38. cout << "YES\n";
  39. } else {
  40. vector<int> foo;
  41. for(int i = 1; i<= pts+1;i++) {
  42. if(next_pts[i].size()>=3)
  43. foo.push_back(i);
  44. }
  45. if(foo.size()<2) {
  46. cout << "NO\n";
  47. }else{
  48.  
  49. size_t i=0;
  50. bool br = false;
  51. while(i < foo.size()-1 && !br) {
  52. size_t j=i+1;
  53. while(j < foo.size() && !br) {
  54. banned_pts.clear();
  55. banned_pts.resize(pts);
  56. for(int k = 0; k<=pts; k++){
  57. for(int l = 0;l<=pts; l++)
  58. banned_pts[k].push_back(false);
  59. }
  60. if(routeFound(foo[i], foo[j], next_pts)) {
  61. found = true;
  62. br = true;
  63. }
  64. j++;
  65. }
  66. i++;
  67. }
  68. if(found)
  69. cout << "YES\n";
  70. else
  71. cout << "NO\n";
  72. }
  73.  
  74. }
  75. }
  76.  
  77. return (0);
  78. }
  79.  
  80. bool routeFound(int pt1, int pt2, vector<int> next_pts[]) {
  81. if(pt1==pt2)
  82. return true;
  83.  
  84. bool res = false;
  85.  
  86. for(size_t i = 0; i<next_pts[pt1].size(); i++) {
  87. if(!banned_pts[pt1][pt2]) {
  88. banned_pts[pt1][pt2] = true;
  89. banned_pts[pt2][pt1] = true;
  90. res = res || routeFound(next_pts[pt1][i], pt2, next_pts);
  91. }
  92. }
  93.  
  94.  
  95. return res;
  96. }
  97.  

Diff to submission s1091

fn.cpp

--- c5.s1091.cteam030.fn.cpp.0.fn.cpp
+++ c5.s1098.cteam030.fn.cpp.0.fn.cpp
@@ -47,8 +47,8 @@
             }else{
                 
-                int i=0;
+                size_t i=0;
                 bool br = false;
                 while(i < foo.size()-1 && !br) {
-                    int j=i+1;
+                    size_t j=i+1;
                     while(j < foo.size() && !br) {
                         banned_pts.clear();
@@ -84,5 +84,5 @@
     bool res = false;
     
-    for(int i = 0; i<next_pts[pt1].size(); i++) {
+    for(size_t i = 0; i<next_pts[pt1].size(); i++) {
         if(!banned_pts[pt1][pt2]) {
             banned_pts[pt1][pt2] = true;