Nearest Opposite Parity （CodeForces - 1272E）（超级源点+反向建边+dijkstra）_codeforce 图论 超级源点 超级汇点

Description

You are given an array aa consisting of nn integers. In one move, you can jump from the position ii to the position i−aii−ai (if 1≤i−ai1≤i−ai) or to the position i+aii+ai (if i+ai≤ni+ai≤n).

For each position ii from 11 to nn you want to know the minimum the number of moves required to reach any position jj such that ajaj has the opposite parity from aiai (i.e. if aiai is odd then ajaj has to be even and vice versa).

Input

The first line of the input contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the number of elements in aa.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤n1≤ai≤n), where aiai is the ii-th element of aa.

Output

Print nn integers d1,d2,…,dnd1,d2,…,dn, where didi is the minimum the number of moves required to reach any position jj such that ajaj has the opposite parity from aiai (i.e. if aiai is odd then ajaj has to be even and vice versa) or -1 if it is impossible to reach such a position.

Example

Input

10
4 5 7 6 7 5 4 4 6 4

Output

1 1 1 2 -1 1 1 3 1 1 

解析：

首先我们添加两个超级源点，将多源最短路转化为单元最短路，并且反向建边。

我们假设超级源点0连接所有的偶点，然后进行一次dijkstra算法求出超级源点0到所有点的最短距离。

假设某个最短路上有一奇点v，那么dis[v]就是对应的答案，因为超级源点0连接的是所有的偶数点，并且是反向建边。

AC代码

#include <bits/stdc++.h>
using namespace std;
 
const int INF = 1 << 30;
const int maxn = 2e5 + 5;
int n, a[maxn];
vector<pair<int, int> >edge[maxn];
int dis[maxn], ans[maxn];
bool vis[maxn];
struct cmp
{
    bool operator () (const pair<int, int> &lhs, const pair<int, int> &rhs)
    {
        return lhs.second > rhs.second;
    }
};
 
void dijkstra(int dir)
{
    for(int i = 0; i < n + 2; i++)
        dis[i] = INF, vis[i] = false;
 
    priority_queue<pair<int, int>, vector<pair<int, int> >, cmp> que;
    que.push(make_pair(dir, 0));
    dis[dir] = 0;
    while(!que.empty())
    {
        pair<int, int> u = que.top();
        que.pop();
 
        if(vis[u.first])
            continue;
 
        vis[u.first] = true;
        for(int i = 0; i < edge[u.first].size(); i++)
        {
            int v = edge[u.first][i].first;
            if(vis[v])
                continue;
            if(dis[v] > dis[u.first] + edge[u.first][i].second)
            {
                dis[v] = dis[u.first] + edge[u.first][i].second;
                que.push(make_pair(v, dis[v]));
            }
        }
    }
}
 
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        if(a[i] + i <= n)
            edge[i + a[i]].push_back(make_pair(i, 1));
        if(i - a[i] >= 1)
            edge[i - a[i]].push_back(make_pair(i, 1));
    }
 
    for(int i = 1; i <= n; i++)
    {
        if(a[i] & 1)
            edge[n + 1].push_back(make_pair(i, 0));
        else
            edge[0].push_back(make_pair(i, 0));
        ans[i] = -1;
    }
 
    dijkstra(0);
    for(int i = 1; i <= n; i++)
        if(a[i] % 2 == 1 && dis[i] != INF)
            ans[i] = dis[i];
 
    dijkstra(n + 1);
    for(int i = 1; i <= n; i++)
        if(a[i] % 2 == 0 && dis[i] != INF)
            ans[i] = dis[i];
 
    for(int i = 1; i <= n; i++)
        printf("%s%d", i == 1 ? "" : " ", ans[i]);
 
    return 0;
}