Description

 

Input

Output

 

Sample Input

5 7 22 31 21 31 42 43 43 54 5

Sample Output

1 2 2 1 2

 

Data Constraint

 

Hint

分析

显然我们对于每个绿洲求spfa即可

（为什么我dij堆优化炸了？？？？）

 

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N=1e5+10;struct Edge {    int v,nx;}g[2*N];int cnt,list[N],d[N],ans[N];bool b[N],gr[N];int n,m,k;void Add(int u,int v) {    g[++cnt].v=v;g[cnt].nx=list[u];list[u]=cnt;}void Spfa(int v0) {    int cnt=1,sum=0;    deque
          
            q;    while (!q.empty()) q.pop_front();    memset(d,0x3f,sizeof d);memset(b,0,sizeof b);    q.push_back(v0);    d[v0]=0;b[v0]=1;    while (!q.empty()) {        int u=q.front();q.pop_front();        if (d[u]*cnt>sum) {            q.push_back(u);            continue;        }        cnt--;sum-=d[u];        for (int i=list[u];i;i=g[i].nx)            if (d[g[i].v]>d[u]+1) {                d[g[i].v]=d[u]+1;                if (!b[g[i].v]) {                    if (!q.empty()&&d[g[i].v]