Sreekar_0125

Untitled

Mar 4th, 2024
609
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.17 KB | None | 0 0
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. const int N = 1e5 + 5;
  9. vector<int> graph[N];
  10. int n;
  11.  
  12. vector<bool> vis(N, 0);
  13.  
  14. vector<int> bfs(int start, int dir)
  15. {
  16.     vector<int> dist(n + 1, 0);
  17.     queue<int> q;
  18.     q.push(start);
  19.     vis[start] = 1;
  20.     while(!q.empty())
  21.     {
  22.         int node = q.front();
  23.         q.pop();
  24.         for(auto i : graph[node])
  25.         {
  26.             if(dir==1 && i <node)continue;
  27.             if(dir==-1 && i>node)continue;
  28.             if(!vis[i])
  29.             {
  30.                 dist[i] = 1 + dist[node];
  31.                 vis[i] = 1;
  32.                 q.push(i);
  33.             }
  34.            
  35.         }
  36.     }
  37.     return dist;
  38. }
  39.  
  40. void dbg(vector<int> &v)
  41. {
  42.     for(auto i : v)
  43.     {
  44.         cerr << i << ' ';
  45.     }
  46.     cerr << endl;
  47. }
  48.  
  49. int main() {
  50.     /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
  51.     int x, y;
  52.     cin >> n >> x >> y;
  53.    
  54.     for(int i = 1; i <= n - 1; i++)
  55.     {
  56.         graph[i].push_back(i + 1);
  57.         graph[i + 1].push_back(i);
  58.     }
  59.    
  60.     graph[x].push_back(y);
  61.     graph[y].push_back(x);
  62.    
  63.     vector<int> distx = bfs(x, 1);
  64.     for(int i = 1; i <= n; i++) vis[i] = false;
  65.    
  66.     vector<int> disty = bfs(y, -1);
  67.    
  68.     vector<int>frex(n+1, 0), frey(n+1, 0);
  69.    
  70.     dbg(distx);
  71.     dbg(disty);
  72.    
  73.     for(int i = 1; i<=n; i++){
  74.        
  75.         frex[distx[i]]++;
  76.         frey[disty[i]]++;
  77.        
  78.     }
  79.    
  80.     dbg(frex);
  81.     dbg(frey);
  82.    
  83.     vector<int> ans(n+1,0);
  84.    
  85.     for(int i = 1; i<=n; i++){
  86.        
  87.            ans[i] += (max(0,(x-i)) + max(0,(n-y-i+1)) + max(0, (y-x+1-i)))*2;
  88.        
  89.     }
  90.     dbg(ans);
  91.    
  92.     frex[1]--; frey[1]--;
  93.    
  94.     ans[1] += (frex[1] + frey[1]);
  95.    
  96.     cout<<ans[1]<<" ";
  97.    
  98.     for(int i = 2; i<=n; i++){
  99.        
  100.         ans[i] += (frex[i-1]*(max(0,x-1)) + frey[i-1]*(max(0,n-y)));
  101.         cout<<ans[i]<<" ";
  102.     }
  103.    
  104.    
  105.    
  106.     cout<<'\n';
  107.     // for(int i = 1; i <= n; i++)
  108.     // {
  109.     //     cerr << dist[i] << " \n"[i == n];
  110.     // }
  111.     return 0;
  112. }
  113.  
Advertisement
Add Comment
Please, Sign In to add comment