BZOJ 4070: [Apio2015]雅加达的摩天楼

Descrption

有\(m\)只doge，每只doge只能到\(b_i+kp_i,k\in Z\)，求0号doge将信息传给1号doge的最少跳跃步数.\(n\leqslant 3\times 10^4\)

Solution

分块.

将\(p\)分成大于\(\sqrt n\)和小于等于\(\sqrt n\)的两部分，然后小于的部分可以暴力建好图再连边，大于的部分直接连所有能到达的位置即可。

复杂度\(O(n\sqrt n)\).

PS:UOJ上过不了Extra Text...

其实时间复杂度没问题...就是有点卡内存...

Code

/**************************************************************
    Problem: 4070
    User: BeiYu
    Language: C++
    Result: Accepted
    Time:8152 ms
    Memory:175408 kb
****************************************************************/
 
#include 
using namespace std;
 
#define uor(i,j,k) for(int i=j;i<=(int)k;i++)
#define uep(i,j,k) for(int i=j;i<(int)k;i++)
 
inline int in(int x=0,char s=getchar()) { while(s>'9'||s<'0')s=getchar();
    while(s>='0'&&s<='9')x=x*10+s-'0',s=getchar();return x; }
 
const int N = 30001;
const int B = 86;
const int NN = N*B+N;
const int M = N*B*5;
const int oo = 0x3f3f3f3f;
 
int n,m,ss,tt,pe;
int to[M],ww[M];
int nxt[M],hd[NN];
int d[NN];
bool b[NN];
 
int get_id(int x,int y) { return x*n+y; }
void AddEdge(int u,int v,int w) 
{ nxt[++pe]=hd[u],to[pe]=v,ww[pe]=w,hd[u]=pe; }
 
int SPFA(int s,int t) {
    memset(d,0x3f,sizeof(d));
    queue q;q.push(s);
    d[s]=0,b[s]=1;
    for(int x;!q.empty();) {
        x=q.front(),q.pop(),b[x]=0;
        for(int i=hd[x];i;i=nxt[i]) {
            int v=to[i],w=ww[i];
            if(d[x]+w";
        uep(j,0,g[i].size()) cout<B) {
            for(int j=1;j*p=0) AddEdge(b,b-j*p,j);
            }
        } else {
            AddEdge(b,get_id(p,b),0);
        }
    }
    for(int i=1;i<=B;i++) for(int j=0;j