Submission #12017

#	Time	Username	Problem	Language	Result	Execution time	Memory
12017		dohyun0324	물병 (JOI14_bottle)	C++98	100 / 100	1320 ms	124880 KiB

bottle

#include<stdio.h>
#include<string.h>
int xx[5]={0,1,0,-1,0};
int yy[5]={0,0,1,0,-1};
int k,t1,t2,r,f,n,m,w,ch[2010][2010],ord[200010],group[200010],lev,pos[2010][2010],tree[400010],top[200010],cnt,tree2[400010],d[21][400010],h[400010],visit[400010];
char a[2010][2010];
struct data
{
    int x,y,p;
}q[4000010];
int up(int x)
{
    if(x==group[x]) return x;
    return group[x]=up(group[x]);
}
void union_find(int x,int y,int val)
{
    int t,r;
    t=up(x); r=up(y);
    if(t==r) return;
    cnt++; tree[top[t]]=cnt; tree[top[r]]=cnt;
    tree2[cnt]=val;
    if(ord[r]<ord[t]) group[r]=group[t], top[t]=cnt;
    if(ord[r]>ord[t]) group[t]=group[r], top[r]=cnt;
    if(ord[r]==ord[t]) group[t]=group[r], ord[r]++, top[r]=cnt;
}
void bfs()
{
    int i,j,kx,ky;
    w=1;
    while(1)
    {
        f++;
        if(f>r)
        {
            for(i=w;i<f;i++)
            {
                for(j=1;j<=4;j++)
                {
                    kx=q[i].x+xx[j]; ky=q[i].y+yy[j];
                    if(a[kx][ky]!='.') continue;
                    if(lev+1==ch[kx][ky]){
                            union_find(pos[kx][ky],q[i].p,lev*2+2); continue;
                    }
                    if(ch[kx][ky]==-1){ r++; q[r].x=kx; q[r].y=ky; q[r].p=q[i].p; ch[kx][ky]=lev+1; pos[kx][ky]=q[r].p;}
                }
            }
            w=f;
            if(f==r+1)
            {
                break;
            }
        }
        lev=ch[q[f].x][q[f].y];
        for(i=1;i<=4;i++)
        {
            kx=q[f].x+xx[i]; ky=q[f].y+yy[i];
            if(a[kx][ky]!='.') continue;
            if(lev==ch[kx][ky])
            {
                union_find(pos[kx][ky],q[f].p,lev*2+1);
            }
        }
    }
}
void LCA(int x,int y)
{
    int i,k;
    if(h[x]>h[y]){
        k=h[x]-h[y];
        for(i=20;i>=0;i--){
            if((1<<i)&k) x=d[i][x];
        }
    }
    if(h[x]<h[y]){
        k=h[y]-h[x];
        for(i=20;i>=0;i--){
            if((1<<i)&k)
            {
                y=d[i][y];
            }
        }
    }
    for(i=20;i>=0;i--)
    {
        if(d[i][x]!=d[i][y]) x=d[i][x], y=d[i][y];
    }
    x=d[0][x];
    printf("%d\n",tree2[x]-1);
}
void dfs(int x)
{
    if(visit[x]){ k=h[x]; return;}
    visit[x]=1;
    dfs(tree[x]);
    h[x]=++k;
}
int main()
{
    int i,j,x,y;
    scanf("%d %d %d %d",&n,&m,&t1,&t2);
    for(i=1;i<=t1;i++) group[i]=i, top[i]=i;
    cnt=t1;
    for(i=1;i<=n;i++) scanf("%s",a[i]+1);
    memset(ch,-1,sizeof ch);
    for(i=1;i<=t1;i++){r++; scanf("%d %d",&q[r].x,&q[r].y); ch[q[r].x][q[r].y]=0; pos[q[r].x][q[r].y]=i; q[r].p=i;}
    bfs(); visit[cnt]=1;
    for(i=1;i<=cnt;i++){k=0; dfs(i);}
    for(i=1;i<=cnt;i++) d[0][i]=tree[i];
    for(i=1;i<=20;i++)
    {
        for(j=1;j<=cnt;j++)
        {
            d[i][j]=d[i-1][d[i-1][j]];
        }
    }
    for(i=1;i<=t2;i++)
    {
        scanf("%d %d",&x,&y);
        LCA(x,y);
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30