2013年6月07日 18:42

BZOJ1266: [AHOI2006]上学路线route【最短路+最小割】

BZOJ

第一问先求1到n的最短路。第二问求破坏一些路使得1到n的最短路变大。每条路被破坏都要花费一定的代价Ci。求min∑Ci。

我学会了写spfa好开心啊!我学会了写dinic好开心啊!==

破坏边使不连通明显最小割水掉嘛、、

好了言归正传、先求出所有的最短路。然后判断每条边是不是在1~n的最短路上。是的话就连边。然后再新建的图上做最小割。

一开始建图建错了、、应该这么建:首先以1为源点跑spfa,记录d[0][i]为1~i的最短路。然后以n为源点跑spfa,记录d[1][i]为n~i的最短路。

如果i在1~n的最短路上那一定满足d[0][i]+d[1][i]==d[0][n](这也是第一问的答案、、)且d[0][i]+w(i,j)=d[0][j]。

然后就没了、、继续fread然后刷到rank5、、、

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxm=250000,maxn=505,inf=2000000009;
struct edge{int t,c,next;}E[maxm];
char buf[3000000],*pt=buf;
int p[maxm],w[maxm],c[maxm],n1[maxm],h[maxn],v[maxn],d[2][maxn],q[maxm],V[maxn],level[maxn],n,m,tot=0,tt=0,S,T,An=inf;
inline int getint(){
    int r=0; while(*pt<'0'||*pt>'9')pt++; while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r;
}inline void ae1(int u,int v,int t,int cc){
    p[tot]=v;   w[tot]=t;   c[tot]=cc;  n1[tot]=h[u];   h[u]=tot++;
    p[tot]=u;   w[tot]=t;   c[tot]=cc;  n1[tot]=h[v];   h[v]=tot++;
}inline void ae2(int a,int b,int c){
    E[tt].t=b; E[tt].c=c; E[tt].next=V[a];   V[a]=tt++;
    E[tt].t=a; E[tt].c=0; E[tt].next=V[b];   V[b]=tt++;
}inline int bfs(){
    memset(level,0xff,sizeof(level));   int head=0,tail=1;  q[0]=S; level[S]=1;
    while(head<tail){
        int u=q[head++];    if(u==T)return 1;
        for(int p=V[u];p!=-1;p=E[p].next)
            if(E[p].c>0 && level[E[p].t]==-1) level[E[p].t]=level[u]+1,q[tail++]=E[p].t;
    }return 0;
}int dfs(int u=S,int lmt=inf){
    if(u==T)    return lmt; int ret=0,  delta;
    for(int p=V[u];p!=-1;p=E[p].next){
        if(E[p].c>0 && level[E[p].t]==level[u]+1){
            delta=dfs(E[p].t,min(lmt-ret,E[p].c));
            E[p].c-=delta;  E[p^1].c+=delta;    ret+=delta;
            if(ret==lmt)    return ret;
        }
    }if(!ret)   level[u]=-1;    return ret;
}inline int dinic(){
    int ret=0;S=1,T=n;
    for(int i=1;i<=n;i++)for(int j=h[i];~j;j=n1[j])
        if(d[0][p[j]]+d[1][p[j]]==An && d[0][i]+w[j]==d[0][p[j]]) ae2(i,p[j],c[j]);
    while(bfs())ret+=dfs(); return ret;
}inline void spfa(int SS,int f){
    for(int i=1;i<=n;i++)d[f][i]=inf; memset(v,0,sizeof(v));
    int head=0,tail=1;  q[0]=SS; v[SS]=1; d[f][SS]=0;
    while(head<tail){
        int u=q[head++];    v[u]=0;
        for(int i=h[u];~i;i=n1[i])
            if(d[f][u]+w[i]<d[f][p[i]]){
                d[f][p[i]]=d[f][u]+w[i];  if(!v[p[i]])  v[p[i]]=1,  q[tail++]=p[i];
            }
    }
}int main(){
    fread(pt,1,3000000,stdin);  n=getint(),m=getint();  memset(h,-1,sizeof(h)); memset(V,-1,sizeof(V));
    for(int u,v,t,c,i=1;i<=m;u=getint(),v=getint(),t=getint(),c=getint(),ae1(u,v,t,c),i++);
    spfa(1,0);  spfa(n,1);  for(int i=1;i<=n;i++)   An=min(An,d[0][i]+d[1][i]);
    printf("%d\n%d\n",An,dinic()); return 0;
}

 

Comments(0)

Tags:

2013年6月07日 16:53

BZOJ1263: [SCOI2006]整数划分【高精度】

BZOJ

果然是3越多越好、、滚回去学小学奥数算了、、、

然后就是高精度了、、比较脑残选择了手写、、更加脑残的选择了压位和快速幂、、然后跑的还行、、

代码越写越短了、、不过还有更短的比不过、、呵呵、、、

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
struct Hugeint{
    ll len,num[10000];  Hugeint(){  len=1ll;  memset(num,0,sizeof(num));}
}An;ll n,two,thr,p[]={1,10,100,1000};
Hugeint Mul(Hugeint a,Hugeint b){
    Hugeint c;  c.len=a.len+b.len+1;
    for(ll i=1;i<=a.len;i++) for(ll j=1;j<=b.len;j++)  c.num[i+j-1]+=a.num[i]*b.num[j];
    for(ll i=1;i<c.len;i++)  if(c.num[i]>9999)  c.num[i+1]+=c.num[i]/10000,  c.num[i]%=10000;
    while(c.num[c.len]>9999) c.len++,  c.num[c.len]+=c.num[c.len-1]/10000,   c.num[c.len-1]%=10000;
    while(c.num[c.len]==0&&c.len>1)  c.len--;   return c;
}Hugeint pow(ll b,ll p){
    Hugeint ans,bb; ans.len=bb.len=ans.num[1]=1ll;  bb.num[1]=b;
    while(p){if(p&1ll)ans=Mul(ans,bb);p>>=1ll;bb=Mul(bb,bb);}   return ans;
}inline int len(int x){
    int r=0; while(x)r++,x/=10; return r;
}void print(Hugeint a){
    if(a.len<=25){ printf("%lld",a.num[a.len]); for(ll i=a.len-1;i;i--)printf("%04lld",a.num[i]); return;} 
    printf("%lld",a.num[a.len]);    for(ll i=a.len-1;i>=a.len-24;i--)printf("%04lld",a.num[i]);
    if(len(a.num[a.len])<4) printf("%lld\n",a.num[a.len-25]/p[len(a.num[a.len])]);
}int main(){
    scanf("%lld",&n); two=0,thr=n/3;  if(n%3)two=2/(n%3),thr=(n-4/(n%3))/3; An=Mul(pow(2,two),pow(3,thr));
    printf("%lld\n",(An.len-1<<2)+len(An.num[An.len])); print(An);  return 0;
}

Comments(0)

Tags:

2013年6月07日 16:08

BZOJ1237: [SCOI2008]配对【贪心+DP】

BZOJ

排序、然后在上下3个中选、dp就好

然后我顺便学了写fread、真好、又快又实用又好写

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll inf=10000000000009LL;
#define abs(x) (((x)<0)?(-(x)):(x))
#define A(x,y) ((x==y)?inf:abs((x)-(y)))
ll n,a[100005],b[100005],f[100005];
char buf[2000000],*p=buf;
inline int getint(){
    ll r=0; while(*p<'0'||*p>'9')p++; while(*p>='0'&&*p<='9')r=r*10+*p++-48;return r;
}int main(){
    fread(p,1,2000000,stdin);
    n=getint(); for(ll i=1;i<=n;i++)a[i]=getint(),b[i]=getint();
    sort(a+1,a+n+1);    sort(b+1,b+n+1);
    f[1]=A(a[1],b[1]);  f[2]=min(f[1]+A(a[2],b[2]),A(a[1],b[2])+A(a[2],b[1]));
    for(ll i=3;i<=n;i++)f[i]=min(f[i-1]+A(a[i],b[i]),min(f[i-2]+A(a[i-1],b[i])+A(a[i],b[i-1]),min(f[i-3]+A(a[i],b[i-1])+A(a[i-1],b[i-2])+A(a[i-2],b[i]),f[i-3]+A(a[i],b[i-2])+A(a[i-1],b[i])+A(a[i-2],b[i-1]))));
    printf("%lld\n",f[n]==inf?-1LL:f[n]);    return 0;
}

Comments(0)

Tags:

2013年6月07日 15:32

BZOJ1260: [CQOI2007]涂色paint【记忆化DP】

BZOJ

类似记忆化dp、、

f[i][j]表示i~j这一段最少要涂几次。每次递归计算、头尾如果相同可以最先涂、所以可以减1、然后合并上来就行、、

最近写的代码怎么都这么短?还是我太弱了只会刷水?唉、、囧、、、

#include<cstdio>
#include<algorithm>
#include<cstring>
const int inf=1000000009;
int F[60][60]={0},l;    char s[60];
int f(int l,int r){
    if(l==r)    return 1;   if(F[l][r]) return F[l][r]; F[l][r]=inf;
    for(int i=l;i<=r;i++)   F[l][r]=std::min(f(l,r),f(l,i)+f(i+1,r));
    return F[l][r]-=(s[l]==s[r]);
}int main(){
    scanf("%s",s);  l=strlen(s);    printf("%d\n",f(0,l-1));   return 0;
} 

Comments(0)

Tags:

2013年6月07日 14:04

BZOJ1270: [BeijingWc2008]雷涛的小猫【DP】

BZOJ

弱弱的dp我也会做!哈哈哈

设f[i][j]表示高度为i时,在第j个树上能吃到的果子数的最大值。m[i]表示高度为i时吃到的果子数的最大值。w[i][j]表示高度为i,第j颗树上的果子树。

那么方程显而易见:f[i][j]=max(f[i+1][j],m[i+d])+w[i][j]。

读入文件好像奇大、好可怕、话说一开始MLE了、、囧不得不开short、、

orz读入优化、瞬间提升5s、





#include<cstdio>
#define max(a,b) (((a)<(b))?(b):(a))
int n,h,d,k,t,i,j,f[5005][5005]={0},m[5005]={0};    short a[5005][5005]={0};
inline void read(int &x){
    char ch;    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    x=ch-'0';   for(ch=getchar();ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
}int main(){
    for(read(n),read(h),read(d),i=1;i<=n;i++)for(read(t),j=1;j<=t;j++)read(k),a[i][k]++;
    for(i=h;~i;i--){
        if(i+d<=h)  t=m[i+d];   else    t=0;
        for(j=1;j<=n;j++)   f[i][j]=max(f[i+1][j],t)+a[j][i],   m[i]=max(m[i],f[i][j]);
    }printf("%d",m[0]); return 0;
}

Comments(0)

Tags:

2013年6月07日 13:59

BZOJ1295: [SCOI2009]最长距离【最短路】

BZOJ

数据范围≤30、、哈哈这么小啊、、

给你一个n*m的点阵、有些点是障碍、求一个欧几里得距离最大的点对(A,B),使得在移走的障碍≤T的情况下,可以从A走到B、

由于数据范围小的出奇那么可以大胆考虑对每个点做一次spfa、连边这样连:(u,v)如果v是障碍那么连的边权就是1、否则连0、每个点都向上下左右各连一条边、接下来跑spfa、要注意一点:如果以一个障碍点为源点开始spfa、那么t要先减一、因为首先得把这个位置上的障碍移掉、然后跑出来每个点的距离就是要移开的障碍数、小于等于T就更新答案即可、

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define pos(x,y) (((x)-1)*m+(y))
int p[10000],w[10000],n1[10000],h[1000],d[1000],q[500000],v[1000],a[40][40],tot=0,n,m,t,An=0;
char s[40]; int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
inline void ae(int a,int b,int c){
    p[tot]=b;   w[tot]=c;   n1[tot]=h[a];  h[a]=tot++;
}inline void spfa(int S){
    memset(d,63,sizeof(d)); memset(v,0,sizeof(v));
    int head=0,tail=1;  q[0]=S; v[S]=1; d[S]=0;
    while(head<tail){
        int u=q[head++];    v[u]=0;
        for(int i=h[u];~i;i=n1[i]){
            if(d[p[i]]>d[u]+w[i]){
                d[p[i]]=d[u]+w[i];
                if(!v[p[i]])    q[tail++]=p[i], v[p[i]]=1;
            }
        }
    }
}inline void build(){
    memset(h,0xff,sizeof(h));
    for(int i=1;i<=n;i++)   for(int j=1;j<=m;j++){
        for(int k=0;k<4;k++){
            int xx=i+dx[k],yy=j+dy[k];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m)  ae(pos(i,j),pos(xx,yy),a[xx][yy]);
        }
    }
}int main(){
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=m;j++)   a[i][j]=s[j]-'0';
    }build();
    for(int i=1;i<=n;i++)   for(int j=1;j<=m;j++){
        spfa(pos(i,j)); t-=a[i][j];
        for(int u=1;u<=n;u++)   for(int v=1;v<=m;v++)
            if(d[pos(u,v)]<=t)  An=max(An,(u-i)*(u-i)+(v-j)*(v-j));
        t+=a[i][j];
    }printf("%.6lf\n",sqrt((double)An));
    return 0;
}

Comments(0)

Tags:

2013年6月07日 11:32

BZOJ1297: [SCOI2009]迷路【矩阵优化】

BZOJ

n个顶点的有向图,每条边的边权都在1~9。问从1到n的长度为t的路径有几条。

看时间10^9立即想到矩乘。而且n≤10,边权范围只有9。那么把每个点都拆成9个。构造01矩阵。

一个点拆成9个之后这9个点首先要连通。然后就是(u,v,w)的边,从(u,w)连一条边到(v,1),最后答案就是Matrix[1][(n,1)]。

复杂度:O(81*n^3*log(t))。rank5、、呵呵、、还不慢、、



#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define pos(x,y) (9*((x)-1)+y)
struct matrix{
    int r,c,num[95][95];
    matrix(){memset(num,0,sizeof(num));};
    matrix(int _r,int _c):r(_r),c(_c){memset(num,0,sizeof(num));};
    inline void setone(){   for(int i=1;i<=r;i++)   num[i][i]=1;}
    matrix operator * (matrix b)const{
        matrix d(r,b.c);    for(int i=1;i<=r;i++)   for(int j=1;j<=b.c;j++){
            for(int k=1;k<=c;k++)   d.num[i][j]+=num[i][k]*b.num[k][j];
            d.num[i][j]%=2009;
        }return d;
    }
}A; int n,t;    char s[12];
matrix operator ^(matrix a,int b){
    matrix d(a.r,a.c);  d.setone();
    while(b){   if(b&1) d=d*a;  b>>=1;  a=a*a;} return d;
}int main(){
    scanf("%d%d",&n,&t);    A.r=A.c=9*n;
    for(int i=1;i<=n;i++)   for(int j=1;j<=8;j++)   A.num[pos(i,j)][pos(i,j+1)]=1;
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=n;j++)   if(s[j]-'0')    A.num[pos(i,s[j]-'0')][pos(j,1)]=1;
    }printf("%d\n",(A^t).num[1][pos(n,1)]);
    return 0;
}

Comments(0)

Tags:

2013年6月07日 00:10

BZOJ1293: [SCOI2009]生日礼物【优先队列/堆】

BZOJ

一直想做一道跟礼物有关的题、于是做了这道、

题意:长度为2^31的数轴上有n(<100w)个不同颜色的点,颜色种类<60,求一个长度最短的区间包含所有颜色的点。

思路好像很快就有了。记录每种颜色出现的第一个点和下一个点、把每种颜色的第一个点放进堆。这算一个初始答案。

之后每次把最左端的点从堆中删除、插入下一个这种颜色的点、直到删除的点没有后继了、那么答案也不能继续更新了(这不是废话?

那么就好了、我比较偷懒就用了priority_queue、、嘿嘿、、、(重载运算符真坑、、被坑了好久、、

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int inf=1000000009;
int d[1000005],h[65],p[1000005],tot=0,L=inf,R=-1,An=inf;
typedef struct gift{
    int x,y;
    gift(){}
    gift(int _x,int _y):x(_x),y(_y){}
    inline bool operator < (gift b)const{
        if(d[x]==d[b.x]){
            if(y==-1)   return 0;   if(b.y==-1) return 1;
            return d[y]>d[b.y];
        }return d[x]>d[b.x];
    }
};
priority_queue<gift>Q;
inline void read(int &x){
    char ch;    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    x=ch-'0';   for(ch=getchar();ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
}int main(){
    int n,k,t,x;    read(n);    read(k);    memset(p,0xff,sizeof(p));
    while(!Q.empty())   Q.pop();
    for(int i=1;i<=k;i++){
        read(t);    read(d[h[i]=tot++]);
        for(int x=h[i],j=2;j<=t;j++,x=p[x])    p[x]=tot++, read(d[p[x]]);
        Q.push(gift(h[i],p[h[i]]));   L=min(L,d[h[i]]),    R=max(R,d[h[i]]);
    }An=R-L;
    while(Q.top().y!=-1){
        gift u=Q.top();    Q.pop();
        if(d[u.y]>R)   R=d[u.y];  Q.push(gift(u.y,p[u.y]));
        if(R-d[Q.top().x]<An)    An=R-d[Q.top().x];
    }printf("%d\n",An);
    return 0;
}

Comments(0)

Tags:

2013年6月03日 21:07

BZOJ1502: [NOI2005]月下柠檬树【Simpson积分】

BZOJ

开始题目什么意思都没看懂。后来明白了是求一些圆和等腰梯形的面积并。

先根据样例画个图。明确算的是哪一部分。

样例图片

最后要求的就是这些图形的面积并了。怎么求呢?需要用到simpson积分公式。由于我太弱所以就讲的意识流一些。或许不是那么严谨吧。

首先要预处理出这些等腰梯形。他们是由相邻两圆的公切线(如果不存在就不用算了)和两条过切点垂直于x轴的线段组成的。这4个点可以通过相似算出。

重点:simpson(l,r)=(f(l)+4f(mid)+f(r))*(r-l)/6. 其中f(x)当然是一个分段函数.每次O(n)可以算出(枚举所有的等腰梯形和圆)

对于定义在[l,r]上的连续函数,求它和x轴、直线x=l、直线x=r围成的面积S=rsimpson(l,r)。当simpson(l,r)=simpson(l,mid)+simpson(mid,r)时,返回simpson(l,r);否则返回rsimpson(l,mid)+rsimpson(mid,r)。显然,答案就是2*simpson(l,r)。

【拓展】

辛普森的简化公式可以用来算体积V:V=h(a+4b+c)/6。

h是立体(常指拟柱体)的高度,a是下底面积,b是中间截面面积(在一半高度上的截面面积),c是上底面积。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-6;
double x[505],r[505],sx[505],sy[505],tx[505],ty[505],L,R,af,t=0;int n;
double f(double xx){
    double fx=0;
    for(int i=1;i<=n+1;i++) if(fabs(xx-x[i])<=r[i]) fx=max(fx,sqrt(r[i]*r[i]-(xx-x[i])*(xx-x[i])));
    for(int i=1;i<=n;i++)   if(x[i+1]-x[i]-fabs(r[i+1]-r[i])>eps && sx[i]<=xx && xx<=tx[i]){
        if(sy[i]<ty[i]) fx=max(fx,sy[i]+(ty[i]-sy[i])*(xx-sx[i])/(tx[i]-sx[i]));
        else            fx=max(fx,ty[i]+(sy[i]-ty[i])*(tx[i]-xx)/(tx[i]-sx[i]));
	}return fx;
}double simpson(double l,double r){
    return (f(l)+f(r)+4*f((l+r)/2.0))*(r-l)/6.0;
}double rsimpson(double l,double r){
    double mid=(l+r)/2.0;
    if(fabs(simpson(l,r)-simpson(l,mid)-simpson(mid,r))<eps)	return simpson(l,mid)+simpson(mid,r);
    return rsimpson(l,mid)+rsimpson(mid,r);
}int main(){
    scanf("%d%lf",&n,&af);  af=1.0/tan(af);
    for(int i=1;i<=n+1;i++) scanf("%lf",&x[i]),t+=x[i],x[i]=t*af;
    for(int i=1;i<=n;i++)   scanf("%lf",&r[i]);L=x[1],R=x[n+1],r[n+1]=0;
    for(int i=1;i<=n;i++){
        L=min(L,x[i]-r[i]), R=max(R,x[i]+r[i]);
        if(x[i+1]-x[i]-fabs(r[i+1]-r[i])>eps){
            double o=(r[i+1]-r[i])/(x[i+1]-x[i]);
            sx[i]=x[i]-r[i]*o,  sy[i]=sqrt(r[i]*r[i]*(1-o*o));
            tx[i]=x[i+1]-r[i+1]*o,  ty[i]=sqrt(r[i+1]*r[i+1]*(1-o*o));
        }
    }printf("%.2lf\n",2*rsimpson(L,R));	return 0;
}

Comments(0)

Tags:

2013年6月03日 14:38

ZOJ2334-Monkey King【二项堆】

ZOJ

这道题网上一搜全是左偏树。囧。因为某天我nc的打开算导看起了二项堆,然后隐隐约约看会了。然后就发现不用二项堆写这道题就不舒服了。囧。
搜到一个用二项堆写的。结果是p党。代码冗长。不忍直视。果断ctrl+w放弃。最后无奈只能在算导的熏陶下自己写了。

言归正传。

题意:一开始n个集合。每个集合里一个数。每次选中两个集合,把这两个个集合的最大值都除以2。然后把这两个集合合并。输出这个集合的最大值。
分析:那么这就是一个最裸的可合并堆的题。

二项堆是一个神奇的东西。所有可并堆的操作都可以O(logn)。打算之后有空学fib堆。那种除了删元素logn其他都O(1)的神器。。
二项堆如果不会请移步算导。
首先要了解二项树。一个包含n个元素的二项堆是由k个二项树组成的。(k=n转化为2进制后数位上1的个数)那么k是logn级别的。
其中每颗二项树都满足堆的性质。比如这道题,每颗二项树的根是整棵二项树中的最大值。那么查询的时候只要遍历一遍二项堆的所有根节点就可以确定最大值。因此查询是O(logn)。
修改的时候。先通过并查集找到两个点对应的二项堆。对这两个堆分别操作:找到最大值的根节点。把这个根对应的值除以2。然后把这整棵二项树提出来。把根节点和子孙全断掉,然后子孙之间反过来拼接到根节点的后面。(具体可以详见算导,这太意识流了)然后再和原来的二项堆合并。合并的时候先归并排序合并O(logn),再进行调整O(logn),因此合并的复杂度是O(logn)。所以整个修改过程都是O(logn)。
那么整道题就是O(nlogn)了。

写了两天才A掉。(一定是我太没效率了。。T.T囧

最后结果出人意料的rank9。尽然把左偏树艹掉了?二项堆神奇啊。或许这是快速读入的胜利?

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100005;
int Fa[maxn],F[maxn],ch[maxn],key[maxn],deg[maxn],n1[maxn],tmp[25],n;
inline int GF(int x){  return x==Fa[x]?x:Fa[x]=GF(Fa[x]);}
inline int UN(int u,int v){
    int uu=GF(u),vv=GF(v);
    if(uu<vv)   Fa[uu]=vv;  else    Fa[vv]=uu;
}inline void link(int x,int y){
    n1[x]=ch[y];    ch[y]=x;    deg[y]++;
}int merge(int x,int y){
    int ret=deg[x]<=deg[y]?x:y,p=ret;
    if(p==x)    x=n1[x];    else    y=n1[y];
    while(x!=-1 || y!=-1){
        if(x==-1)       p=(n1[p]=y),  y=n1[y];
        else if(y==-1)  p=(n1[p]=x),  x=n1[x];
        else{
            if(deg[x]<=deg[y])  p=(n1[p]=x),  x=n1[x];
            else                p=(n1[p]=y),  y=n1[y];
        }
    }n1[p]=-1;  return ret;
}int un(int u,int v){
    if(u==-1)   return v;   if(v==-1)   return u;
    int ret=merge(u,v),p=-1,x=ret,s=n1[x];
    while(s!=-1){
        if(deg[x]!=deg[s] || (n1[s]!=-1 && deg[n1[s]]==deg[x])) p=x,x=s;
        else if(key[x]>=key[s]) n1[x]=n1[s],link(s,x);
        else{
            if(p==-1)  ret=s;   else    n1[p]=s;
            link(x,s);  x=s;
        }s=n1[x];
    }return ret;
}inline int getmax(int head){
    int ret=-1;
    for(int x=head;x!=-1;x=n1[x])   if(key[x]>ret)  ret=key[x];
    return ret;
}void update(int &head){
    int ret=-1,pre=-1,pos,p;
    for(int x=head;x!=-1;pre=x,x=n1[x])   if(key[x]>ret)  ret=key[x],pos=x,p=pre;
    key[pos]>>=1;
    if(deg[pos]){
        if(p==-1){
            head=n1[head];  int tct=0;
            for(int i=ch[pos];i!=-1;i=n1[i])tmp[++tct]=i;
            ch[pos]=-1; n1[pos]=tmp[tct];   int j=tmp[tct];
            for(int i=tct-1;i>=1;i--)n1[j]=tmp[i],j=tmp[i]; n1[j]=-1;
            deg[pos]=0;
            head=un(pos,head);
        }else{
            n1[p]=n1[pos]; int tct=0;
            for(int i=ch[pos];i!=-1;i=n1[i])tmp[++tct]=i;
            ch[pos]=-1; n1[pos]=tmp[tct];   int j=tmp[tct];
            for(int i=tct-1;i>=1;i--)n1[j]=tmp[i],j=tmp[i]; n1[j]=-1;
            deg[pos]=0;
            head=un(pos,head);
        }
    }
}inline void read(int &x){
    char ch;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    x=ch-'0';
    for(ch=getchar();ch>='0' && ch<='9';ch=getchar())x=x*10+ch-'0';
}int main(){
    int m,u,v;
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;i++)read(key[i]),deg[i]=0,ch[i]=n1[i]=-1,F[i]=Fa[i]=i;
        read(m);    
        while(m--){
            read(u);    read(v);
            if(GF(u)==GF(v))  printf("-1\n");
            else{
                update(F[Fa[u]]);   update(F[Fa[v]]);
                int k=un(F[Fa[u]],F[Fa[v]]);    UN(u,v);
                F[Fa[u]]=F[Fa[v]]=k;
                printf("%d\n",getmax(k));
            }
        }
    }return 0;
}

 

Comments(0)

Tags:

Copyright © 2007

Webdesign, tvorba www stránek

Valid XHTML 1.1