注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

Otoci(企鹅岛屿)的程序  

2010-07-23 22:03:42|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
艰难地用一个下午调试完毕。
由于没有code review就直接test,所以几乎所有可能出问题的地方都出了一遍问题。
最终程序秒了标程。

#include <cstdio>
#include <stdlib.h>
#define NMax 30000
using namespace std;
int N;
int P[NMax],uf_fa[NMax],uf_size[NMax];
int fa[NMax][16];
struct edge{
int e;
edge *next;
}epool[NMax+NMax],*etop;
edge *E[NMax];
struct node{
node *fa,*lc,*rc;
int size,weight;
int a,s;
void ini(int x){
fa=lc=rc=NULL;
size=1;weight=rand();
a=s=x;
}
void updata(){
s=a;size=1;
if (lc)s+=lc->s,size+=lc->size;if (rc)s+=rc->s,size+=rc->size;
}
};
node tree[NMax][2];
int list[NMax+NMax][2],lc;
char vi[NMax];
int findp(int a){return uf_fa[a]==-1?a:uf_fa[a]=findp(uf_fa[a]);}
void dfs(int x){
list[lc][0]=x;list[lc][1]=0;lc++;
vi[x]=1;
for (edge *p=E[x];p;p=p->next)if (vi[p->e]){
fa[x][0]=p->e;
for (int j=1;j<16;j++)fa[x][j]=fa[fa[x][j-1]][j-1];
}
for (edge *p=E[x];p;p=p->next){
if (vi[p->e]==0)dfs(p->e);
}
list[lc][0]=x;list[lc][1]=1;lc++;
vi[x]=0;
}
void Ins(node *&r,int where,node *p){
if (r==NULL)r=p;
else{
if (r->lc && r->lc->size>=where || where==0){
Ins(r->lc,where,p);
r->lc->fa=r;
r->updata();
node *q=r->lc;
if (r->weight>q->weight){
q->fa=r->fa;r->fa=q;
r->lc=q->rc;q->rc=r;r=q;
if (q->rc->lc)q->rc->lc->fa=q->rc;
q->rc->updata();q->updata();
}
}else{
Ins(r->rc,where-(r->lc?r->lc->size:0)-1,p);
r->rc->fa=r;
r->updata();
node *q=r->rc;
if (r->weight>q->weight){
q->fa=r->fa;r->fa=q;
r->rc=q->lc;q->lc=r;r=q;
if (q->lc->rc)q->lc->rc->fa=q->lc;
q->lc->updata();q->updata();
}
}
}
}
void MergeTree(int x,int y){
int a=findp(x),b=findp(y);
if (uf_size[a]<uf_size[b]){
int t=x;x=y;y=t;
t=a;a=b;b=t;
}
uf_fa[b]=a;
uf_size[a]+=uf_size[b];
lc=0;
etop->e=y;etop->next=E[x];E[x]=etop;etop++;
etop->e=x;etop->next=E[y];E[y]=etop;etop++;
vi[x]=1;
dfs(y);
vi[x]=0;
node *root;
for (root=tree[x];root->fa;root=root->fa);
int w=0;
node *q=tree[x]->rc;
for (node *p=tree[x];p;q=p,p=p->fa)if (p->rc==q)w+=1+(p->lc?p->lc->size:0);
for (int i=0;i<lc;i++){
if (list[i][1]==0){
tree[list[i][0]][0].ini(P[list[i][0]]);
Ins(root,w+i,tree[list[i][0]]);
while (root->fa)root=root->fa;
}else{
tree[list[i][0]][1].ini(-P[list[i][0]]);
Ins(root,w+i,tree[list[i][0]]+1);
while (root->fa)root=root->fa;
}
}
}
void UpPenguins(int x){
tree[x][0].a=P[x];
for (node *p=tree[x];p;p=p->fa){
p->s=p->a;
if (p->lc)p->s+=p->lc->s;
if (p->rc)p->s+=p->rc->s;
}
tree[x][1].a=-P[x];
for (node *p=tree[x]+1;p;p=p->fa){
p->s=p->a;
if (p->lc)p->s+=p->lc->s;
if (p->rc)p->s+=p->rc->s;
}
}
int Depth(int x){
int ret=0;
for (int i=15;i>=0;i--)if (fa[fa[x][i]][0]!=fa[x][i])
x=fa[x][i],ret+=(1<<i);
while (fa[x][0]!=x)x=fa[x][0],ret++;
return ret;
}
int Lca(int x,int y){
int a=Depth(x),b=Depth(y);
if (a<b){
int t=a;a=b;b=t;
t=x;x=y;y=t;
}
for (int i=0;(1<<i)<=a-b;i++)if ((a-b)&(1<<i))
x=fa[x][i];
for (int l=15;l>=0;l--)if (fa[x][l]!=fa[y][l])
x=fa[x][l],y=fa[y][l];
while (x!=y)x=fa[x][0],y=fa[y][0];
return x;
}
int PathSum(node *p){
int ret=0;
node *q=p->rc;
while (p){
if (p->rc==q)ret+=p->a+(p->lc?p->lc->s:0);
q=p;p=p->fa;
}
return ret;
}
int main()
{
etop=epool;
FILE *fin=fopen("Otoci.in","r"),*fout=fopen("Otoci.out","w");
fscanf(fin,"%d",&N);
for (int i=0;i<N;i++)fscanf(fin,"%d",P+i);
for (int i=0;i<N;i++){
E[i]=NULL;
uf_fa[i]=-1;uf_size[i]=1;
for (int j=0;j<16;j++)fa[i][j]=i;
tree[i][0].ini(P[i]);tree[i][1].ini(-P[i]);
node *tmp=tree[i];
Ins(tmp,1,tree[i]+1);
}
int Q;
fscanf(fin,"%d",&Q);
char buf[20];
for (int i=0;i<N;i++)vi[i]=0;
for (int i=0;i<Q;i++){
int x,y;
fscanf(fin,"%s %d %d",buf,&x,&y);
if (buf[0]=='b'){
x--;y--;
if (findp(x)!=findp(y)){
fprintf(fout,"yes\n");
MergeTree(x,y);
}else fprintf(fout,"no\n");
}else if (buf[0]=='p'){
x--;
P[x]=y;
UpPenguins(x);
}else if (buf[0]=='e'){
x--;y--;
if (findp(x)!=findp(y)){
fprintf(fout,"impossible\n");
}else{
int u=Lca(x,y);
int r=PathSum(tree[x])+PathSum(tree[y])-2*PathSum(tree[u])+P[u];
fprintf(fout,"%d\n",r);
}
}
}
fclose(fin);fclose(fout);
//getchar();
return 0;
}

  评论这张
 
阅读(315)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017