mickypinata

USACO-T014: Wormholes

Nov 26th, 2021 (edited)
298
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: wormhole
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. #define r first
  11. #define c second
  12. typedef pair<int, int> pii;
  13.  
  14. const int N = 12 + 5;
  15.  
  16. enum status {
  17.     UNCHECK, CHECKING, CHECKED
  18. };
  19.  
  20. map<int, int> cols;
  21. vector<pii> adj[N];
  22. pii coor[N];
  23. int permu[N], con[N], n;
  24. status visited[N];
  25.  
  26. bool DFSCycle(int u){
  27.     if(visited[u] == CHECKING){
  28.         return true;
  29.     }
  30.     if(visited[u] == CHECKED){
  31.         return false;
  32.     }
  33.     visited[u] = CHECKING;
  34.     int ur = coor[u].r;
  35.     int uc = coor[u].c;
  36.     int i = cols[uc];
  37.     vector<pii>::iterator itr = upper_bound(adj[i].begin(), adj[i].end(), pii(ur, 1e9));
  38.     if(itr != adj[i].end()){
  39.         int v = itr -> second;
  40.         if(DFSCycle(con[v])){
  41.             return true;
  42.         }
  43.     }
  44.     visited[u] = CHECKED;
  45.     return false;
  46. }
  47.  
  48. int cnt = 0;
  49. void BFCheck(){
  50.     for(int u = 1; u <= n; ++u){
  51.         visited[u] = UNCHECK;
  52.     }
  53.     for(int u = 1; u <= n; ++u){
  54.         if(visited[u] == UNCHECK && DFSCycle(u)){
  55.             ++cnt;
  56.             return;
  57.         }
  58.     }
  59. }
  60.  
  61. void BFRecur(int i){
  62.     if(i > n){
  63.         BFCheck();
  64.         return;
  65.     }
  66.     for(int j = i + 1; j <= n; ++j){
  67.         swap(permu[i + 1], permu[j]);
  68.         con[permu[i]] = permu[i + 1];
  69.         con[permu[i + 1]] = permu[i];
  70.         BFRecur(i + 2);
  71.         swap(permu[i + 1], permu[j]);
  72.     }
  73. }
  74.  
  75. int main(){
  76.  
  77.     freopen("wormhole.in", "r", stdin);
  78.     freopen("wormhole.out", "w", stdout);
  79.  
  80.     scanf("%d", &n);
  81.     int colCnt = 0;
  82.     for(int i = 1; i <= n; ++i){
  83.         int r, c;
  84.         scanf("%d%d", &r, &c);
  85.         coor[i] = pii(r, c);
  86.         map<int, int>::iterator itr = cols.find(c);
  87.         if(itr == cols.end()){
  88.             cols[c] = ++colCnt;
  89.             adj[colCnt].emplace_back(r, i);
  90.         } else {
  91.             adj[itr -> second].emplace_back(r, i);
  92.         }
  93.     }
  94.     for(int i = 1; i <= colCnt; ++i){
  95.         sort(adj[i].begin(), adj[i].end());
  96.     }
  97.     for(int i = 1; i <= n; ++i){
  98.         permu[i] = i;
  99.     }
  100.     BFRecur(1);
  101.     cout << cnt << '\n';
  102.  
  103.     fclose(stdin);
  104.     fclose(stdout);
  105.  
  106.     return 0;
  107. }
  108.  
RAW Paste Data Copied