fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. int n,a[200005],d[200005],vis[200005];
  5. vector <int> ve[200005];
  6. struct cmp
  7. {
  8.     bool operator()(pair <int,int> a, pair <int,int> b)
  9.     {
  10.         return a.second<b.second;
  11.     }
  12. };
  13. void BFS01()
  14. {
  15.     priority_queue <pair<int,int>,vector<pair<int,int>>,cmp> q;
  16.     for (int i=1;i<=n;i++) if (!d[i]) d[i]=1e18;
  17.     for (int i=1;i<=n;i++) if (d[i]==1) q.push({i,1});
  18.     while (q.size())
  19.     {
  20.         int i=q.top().first,j=q.top().second;
  21.         q.pop();
  22.         for (int j : ve[i]) if (d[j]>d[i]+1) d[j]=d[i]+1,q.push({j,d[j]});
  23.     }
  24.     for (int i=1;i<=n;i++) 
  25.     {
  26.         if (d[i]!=1e18) cout<<d[i]<<' ';
  27.         else cout<<-1<<' ';
  28.     }
  29. }
  30. signed main()
  31. {
  32.     ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  33.     cin>>n;
  34.     for (int i=1;i<=n;i++) cin>>a[i];
  35.     for (int i=1;i<=n;i++) 
  36.     {
  37.         if (i-a[i]>=1 && (a[i]+a[i-a[i]])%2==1) d[i]=1;
  38.         if (i+a[i]<=n && (a[i]+a[i+a[i]])%2==1) d[i]=1;
  39.     }
  40.     for (int i=1;i<=n;i++) 
  41.     {
  42.         if (i-a[i]>=1 && (a[i]+a[i-a[i]])%2==0) ve[i-a[i]].push_back(i);
  43.         if (i+a[i]<=n && (a[i]+a[i+a[i]])%2==0) ve[i+a[i]].push_back(i);
  44.     }
  45.     BFS01();
  46.     return 0;
  47. }
Success #stdin #stdout 0.01s 9448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/LvOv6A
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!