PKU 1826 The Best Farm

http://poj.org/problem?id=1826
２次元に散らばった正方形に値が設定されている。
連結な正方形の値の和の最大値を求めろというような問題。

定数倍高速化を頑張る必要があるよう？
queueを配列にしたら通りました。

int ret,c;
int in(){
  while(!isdigit(c=getchar()))
    if(c=='-')return -in();
  ret=c&15;
  while(isdigit(c=getchar()))ret=(ret<<3)+(ret<<1)+(c&15);
  return ret;
}

typedef struct _node{
  int x,y;
  int idx;
  _node * next;
}node;

node ent[200000];
int sz;
const int hashMod=(1<<20)-1;
node* hash[hashMod+1];
int q[300000];
int s,e;

void insert(int x,int y,int idx){
  int ha=((x*1007+y)%hashMod+hashMod)%hashMod;
  for(node*p=hash[ha];p;p=p->next)
    if(p->x==x && p->y==y)return;
  node*p=ent+sz++;
  p->x=x;
  p->y=y;
  p->idx=idx;
  p->next=hash[ha];
  hash[ha]=p;
}

int geti(int x,int y){
  int ha=((x*1007+y)%hashMod+hashMod)%hashMod;  
  for(node*p=hash[ha];p;p=p->next)
    if(p->x==x && p->y==y)return p->idx;
  return -1;
}

int n;
int ix[200000],iy[200000],iv[200000];
bool vis[200000];

void solve(){
  sz=0;
  memset(hash,0,sizeof(hash));
  memset(vis,0,sizeof(vis));

  rep(i,n){
    ix[i]=in();
    iy[i]=in();
    iv[i]=in();
    insert(ix[i],iy[i],i);
  }
  int ans=0;
  rep(i,n){
    if(vis[i])continue;
    s=e=0;
    q[e++]=i;
    int tans=iv[i];
    vis[i]=true;
    while(e-s>0){
      int id=q[s++];
      rep(j,4){
        int nx=ix[id]+dx[j],ny=iy[id]+dy[j];
        int nid=geti(nx,ny);
        if(nid==-1 || vis[nid])continue;
        vis[nid]=true;
        tans+=iv[nid];
        q[e++]=nid;
      }
    }
    ans=max(ans,tans);
  }
  printf("%d\n",ans);
}

main(){
  while(n=in())
    solve();
}