oj.uz

Submission #12016

# Submission time Handle Problem Language Result Execution time Memory
12016 2014-12-17T00:04:49 Z dohyun0324 물병 (JOI14_bottle) C++
70 / 100
 1004 ms 124096 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[100010],group[100010],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 124096 KB Output is correct
2 Correct 4 ms 124096 KB Output is correct
3 Correct 4 ms 124096 KB Output is correct
4 Correct 104 ms 124096 KB Output is correct
5 Correct 100 ms 124096 KB Output is correct
6 Correct 112 ms 124096 KB Output is correct
7 Correct 108 ms 124096 KB Output is correct
8 Correct 112 ms 124096 KB Output is correct
9 Correct 104 ms 124096 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 124096 KB Output is correct
2 Correct 40 ms 124096 KB Output is correct
3 Correct 404 ms 124096 KB Output is correct
4 Correct 560 ms 124096 KB Output is correct
5 Correct 616 ms 124096 KB Output is correct
6 Correct 416 ms 124096 KB Output is correct
7 Correct 568 ms 124096 KB Output is correct
8 Correct 620 ms 124096 KB Output is correct
9 Correct 688 ms 124096 KB Output is correct
10 Correct 412 ms 124096 KB Output is correct
11 Correct 492 ms 124096 KB Output is correct
12 Correct 120 ms 124096 KB Output is correct
13 Correct 256 ms 124096 KB Output is correct
14 Correct 108 ms 124096 KB Output is correct
15 Correct 284 ms 124096 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 124096 KB Output is correct
2 Correct 32 ms 124096 KB Output is correct
3 Correct 332 ms 124096 KB Output is correct
4 Correct 560 ms 124096 KB Output is correct
5 Correct 600 ms 124096 KB Output is correct
6 Correct 676 ms 124096 KB Output is correct
7 Correct 436 ms 124096 KB Output is correct
8 Correct 532 ms 124096 KB Output is correct
9 Correct 132 ms 124096 KB Output is correct
10 Correct 280 ms 124096 KB Output is correct
11 Correct 280 ms 124096 KB Output is correct

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 124096 KB Output is correct
2 Incorrect 1004 ms 124096 KB Output isn't correct
3 Halted 0 ms 0 KB -