YEZAELP

o59_mar_c2_wormholes

Jun 20th, 2021
920
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. const lli INF = 1e18;
  6. const int N = 60;
  7. using pi = pair <int, int>;
  8. using pll = pair <lli, lli>;
  9. using pil = pair <int, lli>;
  10. lli dis[N+10][N+10];
  11. bool vs[N+10][N+10];
  12. pll U[N+10], V[N+10];
  13. vector <pll> coor;
  14. vector <int> g[N+10];
  15. int sz;
  16. void Print();
  17.  
  18. lli Distance(pll u, pll v){
  19.     return abs( u.first - v.first ) + abs( u.second - v.second );
  20. }
  21.  
  22. int index_coor(lli x, lli y){
  23.     int l = 0, r = sz-1;
  24.     while(l <= r){
  25.         int mid = (l + r) / 2;
  26.         if(coor[mid].first == x and coor[mid].second == y) return mid;
  27.         else if(coor[mid].first < x or (coor[mid].first == x and coor[mid].second < y)) l = mid + 1;
  28.         else r = mid - 1;
  29.     }
  30. }
  31.  
  32. int main(){
  33.  
  34.     int m, Q;
  35.     scanf("%d%d", &m, &Q);
  36.  
  37.     for(int i=1;i<=m;i++){
  38.         lli ux, uy, vx, vy;
  39.         scanf("%lld%lld%lld%lld", &ux, &uy, &vx, &vy);
  40.         U[i] = {ux, uy};
  41.         V[i] = {vx, vy};
  42.         coor.push_back({ux, uy});
  43.         coor.push_back({vx, vy});
  44.     }
  45.  
  46.     sort(coor.begin(), coor.end());
  47.     coor.resize( unique(coor.begin(), coor.end()) - coor.begin() );
  48.     sz = coor.size();
  49.  
  50.     for(int i=1;i<=m;i++){
  51.         int idu = index_coor(U[i].first, U[i].second);
  52.         int idv = index_coor(V[i].first, V[i].second);
  53.         g[idu].push_back(idv);
  54.         g[idv].push_back(idu);
  55.     }
  56.  
  57.     for(int i=0;i<sz;i++){
  58.         for(int j=0;j<sz;j++){
  59.             dis[i][j] = INF;
  60.         }
  61.     }
  62.  
  63.     for(int i=0;i<sz;i++){
  64.         priority_queue <pil, vector <pil>, greater <pil>> pq;
  65.         pq.push({0, i});
  66.         dis[i][i] = 0;
  67.         while(!pq.empty()){
  68.             int u = pq.top().second;
  69.             lli d = pq.top().first;
  70.             pq.pop();
  71.             if(vs[i][u]) continue;
  72.             vs[i][u] = true;
  73.             for(auto v: g[u]){
  74.                 dis[i][v] = d;
  75.                 pq.push({dis[i][v], v});
  76.             }
  77.             for(int v=0;v<sz;v++){
  78.                 lli dd = Distance(coor[u], coor[v]);
  79.                 if(!vs[i][v] and d + dd < dis[i][v]){
  80.                     dis[i][v] = d + dd;
  81.                     pq.push({dis[i][v], v});
  82.                 }
  83.             }
  84.         }
  85.     }
  86.  
  87.     for(int q=1;q<=Q;q++){
  88.         lli x1, x2, y1, y2;
  89.         scanf("%lld%lld%lld%lld", &x1, &x2, &y1, &y2);
  90.         lli ans = Distance({x1, x2}, {y1, y2});
  91.         for(int i=0;i<sz;i++){
  92.             for(int j=i+1;j<sz;j++){
  93.                 lli a, b;
  94.                 a = Distance(coor[i], {x1, x2});
  95.                 b = Distance({y1, y2}, coor[j]);
  96.                 ans = min(ans, a + b + dis[i][j]);
  97.                 a = Distance(coor[i], {y1, y2});
  98.                 b = Distance({x1, x2}, coor[j]);
  99.                 ans = min(ans, a + b + dis[i][j]);
  100.             }
  101.         }
  102.         printf("%lld\n", ans);
  103.     }
  104.  
  105.     return 0;
  106. }
  107.  
  108. void Print(){
  109.     for(int i=0;i<sz;i++) printf("%d = (%lld , %lld)\n", i, coor[i].first, coor[i].second);
  110.     for(int i=0;i<sz;i++){
  111.         for(auto v: g[i]){
  112.             printf("%d -> %d\n", i, v);
  113.         }
  114.     }
  115.     for(int i=0;i<sz;i++){
  116.         for(int j=0;j<sz;j++){
  117.             printf("%lld ", dis[i][j]);
  118.         }
  119.         printf("\n");
  120.     }
  121. }
  122.  
RAW Paste Data