Advertisement
YEZAELP

o59_oct_c1_delivery

Mar 18th, 2021
125
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.50 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector <int> g[262155];
  6. const int INF = 2e9;
  7. using pi = pair <int, int>;
  8. int N;
  9. int level[262155];
  10. vector <int> imp;
  11. vector < vector <int>> dis(20, vector <int> (262155, INF));
  12. vector < vector <bool>> visited(20, vector <bool> (262155, false));
  13.  
  14. void setting(int k){
  15.     for(int i = 1; i < 1<<(k-1); i++){
  16.         g[i].push_back(2*i);
  17.         g[2*i].push_back(i);
  18.         g[i].push_back(2*i + 1);
  19.         g[2*i + 1].push_back(i);
  20.         g[i+N/2].push_back(2*i+N/2);
  21.         g[2*i+N/2].push_back(i+N/2);
  22.         g[i+N/2].push_back(2*i+1+N/2);
  23.         g[2*i+1+N/2].push_back(i+N/2);
  24.     }
  25.     for(int i = 1; i < 1<<k; i++)
  26.         level[i] = level[i/2] + 1;
  27. }
  28.  
  29. void distance(int i){
  30.     priority_queue <pi, vector <pi>, greater <pi>> pq;
  31.     pq.push({0, imp[i]});
  32.     dis[i][imp[i]] = 0;
  33.     while(pq.size() > 0){
  34.         int u, d;
  35.         d = pq.top().first;
  36.         u = pq.top().second;
  37.         pq.pop();
  38.         if(visited[i][u])
  39.             continue;
  40.         visited[i][u] = true;
  41.         for(auto v: g[u]){
  42.             if(!visited[i][v] and d+1 < dis[i][v]){
  43.                 dis[i][v] = d + 1;
  44.                 pq.push({d+1, v});
  45.             }
  46.         }
  47.     }
  48. }
  49.  
  50. int tree(int u, int v, int mod){
  51.     u = u % mod;
  52.     v = v % mod;
  53.     if(level[v] < level[u]) swap(u, v); // level[u] < level[v]
  54.     int cnt = 0;
  55.     while(level[v] != level[u]){
  56.         cnt ++;
  57.         v = v/2;
  58.     }
  59.     while(u != v){
  60.         u = u/2;
  61.         v = v/2;
  62.         cnt += 2;
  63.     }
  64.     return cnt;
  65. }
  66.  
  67. int main(){
  68.  
  69.     int k, l, Q;
  70.     scanf("%d%d%d", &k, &l, &Q);
  71.  
  72.     N = 1 << (k+1);
  73.  
  74.     setting(k);
  75.  
  76.     for(int i=0;i<l;i++){
  77.         int a, b;
  78.         scanf("%d%d", &a, &b);
  79.         g[a].push_back(b);
  80.         g[b].push_back(a);
  81.         imp.push_back(a);
  82.         imp.push_back(b);
  83.     }
  84.  
  85.     /*for(int u = 1; u <= N; u++){
  86.         printf("%d : ", u);
  87.         for(auto v: g[u]) printf("%d ", v);
  88.         printf("\n");
  89.     }*/
  90.  
  91.     for(int i=0;i<2*l;i++){
  92.         distance(i);
  93.         /*for(int j=1;j<=N;j++){
  94.             printf("%d ", dis[i][j]);
  95.         }
  96.         printf("\n");*/
  97.     }
  98.  
  99.     while(Q--){
  100.         int x, y;
  101.         scanf("%d%d", &x, &y);
  102.         int ans = INF;
  103.         if((x < (1<<k) and y < (1 << k)) or (x > (1<<k) and y > (1<<k))) ans = tree(x, y, 1<<k);
  104.         for(int i=0;i<2*l;i++){
  105.             ans = min(ans, dis[i][x] + dis[i][y]);
  106.         }
  107.         printf("%d\n", ans);
  108.     }
  109.  
  110.     return 0;
  111. }
  112.  
Advertisement
RAW Paste Data Copied
Advertisement