Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cmath>
- #include <cstdio>
- #include <vector>
- #include <iostream>
- #include <algorithm>
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 1e5 + 5;
- vector<int> graph[N];
- int n;
- vector<bool> vis(N, 0);
- vector<int> bfs(int start, int dir)
- {
- vector<int> dist(n + 1, 0);
- queue<int> q;
- q.push(start);
- vis[start] = 1;
- while(!q.empty())
- {
- int node = q.front();
- q.pop();
- for(auto i : graph[node])
- {
- if(dir==1 && i <node)continue;
- if(dir==-1 && i>node)continue;
- if(!vis[i])
- {
- dist[i] = 1 + dist[node];
- vis[i] = 1;
- q.push(i);
- }
- }
- }
- return dist;
- }
- void dbg(vector<int> &v)
- {
- for(auto i : v)
- {
- cerr << i << ' ';
- }
- cerr << endl;
- }
- int main() {
- /* Enter your code here. Read input from STDIN. Print output to STDOUT */
- int x, y;
- cin >> n >> x >> y;
- for(int i = 1; i <= n - 1; i++)
- {
- graph[i].push_back(i + 1);
- graph[i + 1].push_back(i);
- }
- graph[x].push_back(y);
- graph[y].push_back(x);
- vector<int> distx = bfs(x, 1);
- for(int i = 1; i <= n; i++) vis[i] = false;
- vector<int> disty = bfs(y, -1);
- vector<int>frex(n+1, 0), frey(n+1, 0);
- dbg(distx);
- dbg(disty);
- for(int i = 1; i<=n; i++){
- frex[distx[i]]++;
- frey[disty[i]]++;
- }
- dbg(frex);
- dbg(frey);
- vector<int> ans(n+1,0);
- for(int i = 1; i<=n; i++){
- ans[i] += (max(0,(x-i)) + max(0,(n-y-i+1)) + max(0, (y-x+1-i)))*2;
- }
- dbg(ans);
- frex[1]--; frey[1]--;
- ans[1] += (frex[1] + frey[1]);
- cout<<ans[1]<<" ";
- for(int i = 2; i<=n; i++){
- ans[i] += (frex[i-1]*(max(0,x-1)) + frey[i-1]*(max(0,n-y)));
- cout<<ans[i]<<" ";
- }
- cout<<'\n';
- // for(int i = 1; i <= n; i++)
- // {
- // cerr << dist[i] << " \n"[i == n];
- // }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment