time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given an array a consisting of n integers. In one move, you can jump from the position i to the position i−ai (if 1≤i−ai) or to the position i+ai (if i+ai≤n).
For each position i from 1 to n you want to know the minimum the number of moves required to reach any position j such that aj has the opposite parity from ai (i.e. if ai is odd then aj has to be even and vice versa).
input
10 4 5 7 6 7 5 4 4 6 4
output
1 1 1 2 -1 1 1 3 1 1
/// spfa最最短路，建立两个超级源点，一个连接奇数点一个链接偶数点，在建边的时候，边权设置为 1
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e6 + 7; typedef int itn; int n; int a[maxn]; struct Node{ int u; int v; int next; int w; }edge[maxn]; int cnt; int head[maxn]; int dis[maxn]; itn ans[maxn]; itn vis[maxn]; void _Init(){ cnt = 0; for(int i=0;i<maxn;i++) head[i] = -1; } void _Add(int u,int v){ edge[cnt].u = u; edge[cnt].v = v; edge[cnt].w = 1; edge[cnt].next = head[u]; head[u] = cnt ++; } void _SPFA(int u){ for(int i=1;i<maxn;i++){ dis[i] = 0x3f3f3f3f; vis[i] = 0; } dis[u] = 0; vis[u] = 1; queue<int> que; ///cout << que.size() <<endl; que.push(u); while(que.size()){ int t = que.front(); que.pop(); vis[t] = 0; for(int i = head[t]; ~i;i = edge[i].next){ int to = edge[i].v; if(dis[to] > dis[t] + edge[i].w){ dis[to] = dis[t] + edge[i].w; if(vis[to] == 0){ que.push(to); vis[to] = 1; } } ///puts("ok"); } } } int main(){ cin >> n; _Init(); for(int i=1;i<=n;i++) cin >> a[i]; for(int i=1;i<=n;i++){ if(i - a[i] >= 1) _Add(i - a[i],i); if(i + a[i] <= n) _Add(i + a[i],i); if(a[i] % 2 == 0) _Add(n+1,i); else _Add(n+2,i); } _SPFA(n + 1); ///puts("okay"); for(int i=1;i<=n;i++){ if(a[i] % 2) ans[i] = dis[i]; } _SPFA(n + 2); for(int i=1;i<=n;i++){ if(a[i] % 2 == 0) ans[i] = dis[i]; } for(int i=1;i<=n;i++){ if(ans[i] == 0x3f3f3f3f) printf("-1 "); else printf("%d ",ans[i] - 1); } ///cout << 0x3f3f3f3f <<endl; return 0; }
