oj.uz

Submission #12017

# Submission time Handle Problem Language Result Execution time Memory
12017 2014-12-17T00:06:51 Z dohyun0324 물병 (JOI14_bottle) C++
100 / 100
 1320 ms 124880 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 124880 KB Output is correct
2 Correct 0 ms 124880 KB Output is correct
3 Correct 0 ms 124880 KB Output is correct
4 Correct 108 ms 124880 KB Output is correct
5 Correct 100 ms 124880 KB Output is correct
6 Correct 96 ms 124880 KB Output is correct
7 Correct 96 ms 124880 KB Output is correct
8 Correct 100 ms 124880 KB Output is correct
9 Correct 80 ms 124880 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 124880 KB Output is correct
2 Correct 48 ms 124880 KB Output is correct
3 Correct 388 ms 124880 KB Output is correct
4 Correct 548 ms 124880 KB Output is correct
5 Correct 636 ms 124880 KB Output is correct
6 Correct 396 ms 124880 KB Output is correct
7 Correct 564 ms 124880 KB Output is correct
8 Correct 620 ms 124880 KB Output is correct
9 Correct 688 ms 124880 KB Output is correct
10 Correct 424 ms 124880 KB Output is correct
11 Correct 492 ms 124880 KB Output is correct
12 Correct 116 ms 124880 KB Output is correct
13 Correct 296 ms 124880 KB Output is correct
14 Correct 116 ms 124880 KB Output is correct
15 Correct 264 ms 124880 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 124880 KB Output is correct
2 Correct 32 ms 124880 KB Output is correct
3 Correct 332 ms 124880 KB Output is correct
4 Correct 572 ms 124880 KB Output is correct
5 Correct 644 ms 124880 KB Output is correct
6 Correct 696 ms 124880 KB Output is correct
7 Correct 436 ms 124880 KB Output is correct
8 Correct 520 ms 124880 KB Output is correct
9 Correct 124 ms 124880 KB Output is correct
10 Correct 288 ms 124880 KB Output is correct
11 Correct 264 ms 124880 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 124880 KB Output is correct
2 Correct 1020 ms 124880 KB Output is correct
3 Correct 460 ms 124880 KB Output is correct
4 Correct 1176 ms 124880 KB Output is correct
5 Correct 1320 ms 124880 KB Output is correct
6 Correct 732 ms 124880 KB Output is correct
7 Correct 428 ms 124880 KB Output is correct
8 Correct 112 ms 124880 KB Output is correct
9 Correct 984 ms 124880 KB Output is correct
10 Correct 788 ms 124880 KB Output is correct
11 Correct 980 ms 124880 KB Output is correct
12 Correct 852 ms 124880 KB Output is correct