Advertisement
SansPapyrus683

USACO Wormholes Solution

Jan 26th, 2022
902
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <fstream>
  4. #include <algorithm>
  5.  
  6. using std::cout;
  7. using std::endl;
  8. using std::vector;
  9.  
  10. struct Point {
  11.     int x;
  12.     int y;
  13. };
  14.  
  15. class Wormholes {
  16.     private:
  17.         const vector<Point>& wormholes;
  18.         vector<int> to_the_right;
  19.         vector<int> partners;
  20.     public:
  21.         Wormholes(const vector<Point>& wormholes)
  22.                 : wormholes(wormholes),
  23.                   to_the_right(wormholes.size(), -1),
  24.                   partners(wormholes.size(), -1) {
  25.             for (int w = 0; w < wormholes.size(); w++) {
  26.                 vector<int> poss_next;
  27.                 for (int ow = 0; ow < wormholes.size(); ow++) {
  28.                     if (wormholes[w].y == wormholes[ow].y
  29.                             && wormholes[w].x < wormholes[ow].x) {
  30.                         poss_next.push_back(ow);
  31.                     }
  32.                 }
  33.                 std::sort(
  34.                     poss_next.begin(), poss_next.end(), [&] (int w1, int w2) {
  35.                     return wormholes[w1].x < wormholes[w2].x;
  36.                 });
  37.                 if (!poss_next.empty()) {
  38.                     to_the_right[w] = poss_next.front();
  39.                 }
  40.             }
  41.         }
  42.  
  43.         int count_valid() {
  44.             // cout << partners << endl;
  45.             bool all_paired = true;
  46.             int w = 0;
  47.             for (; w < wormholes.size(); w++) {
  48.                 if (partners[w] == -1) {
  49.                     all_paired = false;
  50.                     break;
  51.                 }
  52.             }
  53.             if (all_paired) {
  54.                 return inf_loop_possible();
  55.             }
  56.  
  57.             int total = 0;
  58.             for (int ow = w + 1; ow < wormholes.size(); ow++) {
  59.                 if (partners[ow] == -1) {
  60.                     partners[w] = ow;
  61.                     partners[ow] = w;
  62.                     total += count_valid();
  63.                     partners[w] = partners[ow] = -1;
  64.                 }
  65.             }
  66.             return total;
  67.         }
  68.  
  69.         bool inf_loop_possible() {
  70.             for (int s = 0; s < wormholes.size(); s++) {
  71.                 int pos = s;
  72.                 for (int i = 0; i < wormholes.size(); i++) {
  73.                     if (to_the_right[pos] == -1) {
  74.                         break;
  75.                     }
  76.                     pos = partners[to_the_right[pos]];
  77.                     if (pos == s) {
  78.                         return true;
  79.                     }
  80.                 }
  81.             }
  82.             return false;
  83.         }
  84. };
  85.  
  86. int main() {
  87.     std::ifstream read("wormhole.in");
  88.  
  89.     int wormhole_num;
  90.     read >> wormhole_num;
  91.     vector<Point> wormholes(wormhole_num);
  92.     for (Point& p : wormholes) {
  93.         read >> p.x >> p.y;
  94.     }
  95.  
  96.     std::ofstream("wormhole.out") << Wormholes(wormholes).count_valid() << endl;
  97. }
  98.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement