题意描述
思路
对于
u
u
u和
v
v
v之间的一条边，我们要求的是在
v
v
v的基础上来更新
u
u
u，如果正向建边，则是在
u
u
u的基础上更新
v
v
v，所以这道题我们可以反向建边。然后将所有点都加入队列，
b
f
s
bfs
bfs求出对于每个点与偶数的最近距离和奇数的最近距离即可。
AC代码
#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std
;
typedef unsigned long long ull
;
typedef pair
<int,int> PII
;
typedef pair
<long,long> PLL
;
typedef pair
<char,char> PCC
;
typedef long long ll
;
const int N
=2*1e5+10;
const int M
=1e6+10;
const int INF
=0x3f3f3f3f;
const int MOD
=1e9+7;
int n
,a
[N
],d
[N
];
vector
<int> g
[N
];
struct node
{
int odd_d
,even_d
,u
;
}Node
[N
];
void bfs(){
queue
<int> q
;
rep(i
,1,n
+1) q
.push(i
);
while(q
.size()){
int t
=q
.front();q
.pop();
rep(i
,0,sz(g
[t
])){
int v
=g
[t
][i
];
if(Node
[t
].u
&1){
if(Node
[v
].odd_d
>1 || Node
[v
].even_d
>Node
[t
].even_d
+1){
Node
[v
].odd_d
=1;
if(Node
[v
].even_d
>Node
[t
].even_d
+1) Node
[v
].even_d
=Node
[t
].even_d
+1;
q
.push(v
);
}
}else{
if(Node
[v
].even_d
>1 || Node
[v
].odd_d
>Node
[t
].odd_d
+1){
Node
[v
].even_d
=1;
if(Node
[v
].odd_d
>Node
[t
].odd_d
+1) Node
[v
].odd_d
=Node
[t
].odd_d
+1;
q
.push(v
);
}
}
}
}
}
void solve(){
cin
>>n
;
rep(i
,1,n
+1){
Node
[i
].odd_d
=Node
[i
].even_d
=INF
;
cin
>>Node
[i
].u
;
if(i
+Node
[i
].u
<=n
) g
[i
+Node
[i
].u
].PB(i
);
if(i
-Node
[i
].u
>=1) g
[i
-Node
[i
].u
].PB(i
);
}
bfs();
rep(i
,1,n
+1){
if(Node
[i
].u
&1) cout
<<(Node
[i
].even_d
==INF
? -1 : Node
[i
].even_d
)<<' ';
else cout
<<(Node
[i
].odd_d
==INF
? -1 : Node
[i
].odd_d
)<<' ';
}
cout
<<endl
;
}
int main(){
IOS
;
solve();
return 0;
}
