Source code for submission s1134

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+2);
  56.                         for(int k = 0; k<=pts; k++){
  57.                             banned_pts[k].clear();
  58.                             for(int l = 0;l<=pts; l++)
  59.                                 banned_pts[k].push_back(false);
  60.                         }
  61.                         if(routeFound(foo[i], foo[j], next_pts)) {
  62.                             found = true;
  63.                             br = true;
  64.                         }
  65.                         j++;
  66.                     }
  67.                     i++;
  68.                 }
  69.                 if(found)
  70.                     cout << "YES\n";
  71.                 else
  72.                     cout << "NO\n";
  73.             }
  74.  
  75.         }
  76.     }
  77.  
  78.     return (0);
  79. }
  80.  
  81. bool routeFound(int pt1, int pt2, vector<int> next_pts[]) {
  82.     if(pt1==pt2)
  83.         return true;
  84.  
  85.     bool res = false;
  86.  
  87.     for(size_t i = 0; i<next_pts[pt1].size(); i++) {
  88.         if(!banned_pts[pt1][pt2]) {
  89.             banned_pts[pt1][pt2] = true;
  90.             banned_pts[pt2][pt1] = true;
  91.             res = res || routeFound(next_pts[pt1][i], pt2, next_pts);
  92.         }
  93.     }
  94.  
  95.  
  96.     return res;
  97. }
  98.  

Diff to submission s1098

fn.cpp

--- c5.s1098.cteam030.fn.cpp.0.fn.cpp
+++ c5.s1134.cteam030.fn.cpp.0.fn.cpp
@@ -53,6 +53,7 @@
                     while(j < foo.size() && !br) {
                         banned_pts.clear();
-                        banned_pts.resize(pts);
+                        banned_pts.resize(pts+2);
                         for(int k = 0; k<=pts; k++){
+                            banned_pts[k].clear();
                             for(int l = 0;l<=pts; l++)
                                 banned_pts[k].push_back(false);