Submission #594973

# Submission time Handle Problem Language Result Execution time Memory
594973 2022-07-13T08:15:15 Z 조영욱(#8439) 물병 (JOI14_bottle) C++14
10 / 100
4897 ms 524288 KB
#include <bits/stdc++.h>
using namespace std;

int n,m,pp,q;
typedef pair<int,int> P;
char arr[2000][2001]; //4
int xp[200000];
int yp[200000];
int s[200000];
int t[200000];
int lo[200000]; //�Ұ���
int hi[200000]; //����
int mid[200000]; //5
int dist[4001][4001]; //64
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int p[16200000]; //64
vector<P> vec; //10
int lrx[6]={-1,0,1,1,0,-1};
int lry[6]={-1,-2,-1,1,2,1};
int udx[6]={-1,-2,-1,1,2,1};
int udy[6]={1,0,-1,-1,0,1};
int ret[200000]; //1
int val[4000000]; //16
typedef pair<P,int> Pi;
Pi edge[8000000]; //96
int st[4000000]; //16
int ss=0;
int f=0;
int top[4000000]; //16
int ind[4000000]; //16
int par[4000000]; //16
int chk=0;
P que[16200000]; //128
int qs=0;
int qe=-1;

const int siz=(1<<22);
int seg[siz*2]; //32

int sum(int l,int r,int node=1,int nodel=0,int noder=siz-1) {
    if (r<nodel||l>noder) {
        return 0;
    }
    if (l<=nodel&&noder<=r) {
        return seg[node];
    }
    int mid=(nodel+noder)/2;
    return max(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
}

void update(int i,int val) {
    i+=siz;
    seg[i]=val;
    while (i>1) {
        i/=2;
        seg[i]=max(seg[i*2],seg[i*2+1]);
    }
}


void dfs_sz(int v,int prev) {
    par[v]=prev;
    seg[v]=1;
    for(int i=st[v];i<chk;i++) {
        if (edge[i].first.first!=v) {
            break;
        }
        int nt=edge[i].first.second;
        if (nt==prev) {
            continue;
        }
        val[nt]=edge[i].second;
        que[ss++]=P(v,nt);
        dfs_sz(nt,v);
        seg[v]+=seg[nt];
    }
}

void dfs_hld(int v) {
    ind[v]=f++;
    update(ind[v],val[v]);
    if (st[v]==-1) {
        return;
    }
    for(int i=st[v];i<ss;i++) {
        if (que[i].first!=v) {
            break;
        }
        int nt=que[i].second;
        if (i==st[v]) {
            top[nt]=top[v];
            dfs_hld(nt);
        }
        else {
            top[nt]=nt;
            dfs_hld(nt);
        }
    }
}

int query(int u,int v) {
int cnt=0;
    int ret=0;
    while (1) {
        if (top[u]==top[v]) {
            break;
        }
        if (ind[top[u]]>ind[top[v]]) {
            ret=max(ret,sum(ind[top[u]],ind[u]));
            u=par[top[u]];
        }
        else {
            ret=max(ret,sum(ind[top[v]],ind[v]));
            v=par[top[v]];
        }
    }
    if (ind[u]<ind[v]) {
        swap(u,v);
    }
    ret=max(ret,sum(ind[v]+1,ind[u]));
    return ret;
}

bool valid(int x,int y) {
    return x>=0&&x<n&&y>=0&&y<m&&arr[x][y]!='#';
}

bool valid1(int x,int y) {
    return x>=0&&x<=2*n&&y>=0&&y<=2*m;
}

int find(int a) {
    return p[a]<0?a:p[a]=find(p[a]);
}

void merge(int a,int b) {
    a=find(a);
    b=find(b);
    if (a==b) {
        return;
    }
    p[b]=a;
}
int main(void) {
    scanf("%d %d %d %d",&n,&m,&pp,&q);
    for(int i=0;i<n;i++) {
        scanf("%s",arr[i]);
    }
    for(int i=0;i<pp;i++) {
        scanf("%d %d",&xp[i],&yp[i]);
        xp[i]--;
        yp[i]--;
    }
    for(int i=0;i<q;i++) {
        scanf("%d %d",&s[i],&t[i]);
        s[i]--;
        t[i]--;
    }
    for(int i=0;i<q;i++) {
        lo[i]=0;
        hi[i]=((n*m)/2+1)*2;
    }
    //int chk=0;
    if (true) {
        bool flag=true;
        int cnt=0;
        memset(dist,-1,sizeof(dist));
        for(int i=0;i<n*m;i++) {
            p[i]=-1;
        }
        for(int i=0;i<pp;i++) {
            que[++qe]=P(xp[i],yp[i]);
            //vis[xp[i]][yp[i]]=true;
            dist[xp[i]][yp[i]]=0;
        }
        for(int i=1;i<n*m;i++) {
            while (qs<=qe) {
                P now=que[qs];
                if (dist[now.first][now.second]>=i) {
                    break;
                }
                qs++;
                int x=now.first;
                int y=now.second;
                for(int j=0;j<4;j++) {
                    if (valid(x+dx[j],y+dy[j])) {
                        int nt=(x+dx[j])*m+y+dy[j];
                        if (find(x*m+y)!=find(nt)) {
                            edge[chk++]=Pi(P(x*m+y,nt),i);
                            edge[chk++]=Pi(P(nt,x*m+y),i);
                            merge(x*m+y,nt);
                        }
                        if (dist[x+dx[j]][y+dy[j]]==-1) {
                            que[++qe]=P(x+dx[j],y+dy[j]);
                            dist[x+dx[j]][y+dy[j]]=dist[x][y]+1;
                        }
                    }
                }
            }
        }
        qs=0;
        qe=-1;
        for(int i=0;i+1<n*m;i++) {
            if (find(i)!=find(i+1)) {
                edge[chk++]=Pi(P(i,i+1),((n*m)/2+1));
                edge[chk++]=Pi(P(i+1,i),((n*m)/2+1));
                merge(i,i+1);
            }
        }
        sort(edge,edge+chk);
        memset(st,-1,sizeof(st));
        for(int i=chk-1;i>=0;i--) {
            st[edge[i].first.first]=i;
        }
        dfs_sz(0,-1);
        top[0]=0;
        sort(que,que+ss);
        memset(st,-1,sizeof(st));
        for(int i=ss-1;i>=0;i--) {
            st[que[i].first]=i;
        }
        for(int i=0;i<n*m;i++) {
            if (st[i]==-1) {
                continue;
            }
            for(int j=st[i];j<ss;j++) {
                if (que[j].first!=i) {
                    break;
                }
                int pr=st[i];
                if (seg[que[pr].second]<seg[que[j].second]) {
                    swap(que[pr],que[j]);
                }
            }
        }
        memset(seg,0,sizeof(seg));
        dfs_hld(0);
        for(int i=0;i<q;i++) {
            int one=s[i];
            int two=t[i];
            int got=query(xp[one]*m+yp[one],xp[two]*m+yp[two]);
            lo[i]=2*got-2;
            hi[i]=2*got;
        }
    }
    memset(dist,-1,sizeof(dist));
    memset(p,-1,sizeof(p));
    int cnt=0;
    for(int i=0;i<q;i++) {
//printf("%d %d\n",lo[i],hi[i]);
if (hi[i]==((n*m)/2+1)*2) {
ret[i]=0;
continue;
}
        vec.push_back(P((lo[i]+1)/2,i));
        cnt++;
    }
    sort(vec.begin(),vec.end());
    int len=2*m+1;
    for(int i=0;i<pp;i++) {
        for(int j=0;j<4;j++) {
            int nx=2*xp[i]+1+dx[j];
            int ny=2*yp[i]+1+dy[j];
            merge((2*xp[i]+1)*len+(2*yp[i]+1),nx*len+ny);
            if (dist[nx][ny]==-1) {
                que[++qe]=P(nx,ny);
                dist[nx][ny]=0;
            }
        }
    }
    int idx=0;
    for(int i=0;cnt;i++) {
        while (idx<vec.size()&&vec[idx].first==i) {
            int one=s[vec[idx].second];
            int two=t[vec[idx].second];
            cnt--;
            if (find((2*xp[one]+1)*len+(2*yp[one]+1))==find((2*xp[two]+1)*len+(2*yp[two]+1))) {
                ret[vec[idx].second]=2*i+1;
            }
            else {
                ret[vec[idx].second]=2*i+2;
            }
            idx++;
        }
        if (cnt==0) {
            break;
        }
//printf("%d\n",i);
        while (qs<=qe) {
            P now=que[qs];
            if (dist[now.first][now.second]>i) {
                break;
            }
            qs++;
            int x=now.first;
            int y=now.second;
            if (x%2==1) {
                for(int j=0;j<6;j++) {
                    if (valid1(x+lrx[j],y+lry[j])) {
                        int nx=x+lrx[j];
                        int ny=y+lry[j];
                        if (j<3) {
                            if (arr[x/2][y/2-1]!='#') {
//printf("%d %d %d %d\n",x,y,nx,ny);
                                merge(x*len+y,nx*len+ny);
                                if (dist[nx][ny]==-1) {
                                    que[++qe]=P(nx,ny);
                                    dist[nx][ny]=dist[x][y]+1;
                                }
                            }
                        }
                        else {
                            if (arr[x/2][y/2]!='#') {
//printf("%d %d %d %d\n",x,y,nx,ny);
                                merge(x*len+y,nx*len+ny);
                                if (dist[nx][ny]==-1) {
                                    que[++qe]=P(nx,ny);
                                    dist[nx][ny]=dist[x][y]+1;
                                }
                            }
                        }
                    }
                }
            }
            else {
                for(int j=0;j<6;j++) {
                    if (valid1(x+udx[j],y+udy[j])) {
                        int nx=x+udx[j];
                        int ny=y+udy[j];
                        if (j<3) {
                            if (arr[x/2-1][y/2]!='#') {
//printf("%d %d %d %d\n",x,y,nx,ny);
                                merge(x*len+y,nx*len+ny);
                                if (dist[nx][ny]==-1) {
                                    que[++qe]=P(nx,ny);
                                    dist[nx][ny]=dist[x][y]+1;
                                }
                            }
                        }
                        else {
                            if (arr[x/2][y/2]!='#') {
//printf("%d %d %d %d\n",x,y,nx,ny);
                                merge(x*len+y,nx*len+ny);
                                if (dist[nx][ny]==-1) {
                                    que[++qe]=P(nx,ny);
                                    dist[nx][ny]=dist[x][y]+1;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    for(int i=0;i<q;i++) {
        printf("%d\n",ret[i]-1);
    }
}

Compilation message

bottle.cpp: In function 'int query(int, int)':
bottle.cpp:103:5: warning: unused variable 'cnt' [-Wunused-variable]
  103 | int cnt=0;
      |     ^~~
bottle.cpp: In function 'int main()':
bottle.cpp:166:14: warning: unused variable 'flag' [-Wunused-variable]
  166 |         bool flag=true;
      |              ^~~~
bottle.cpp:167:13: warning: unused variable 'cnt' [-Wunused-variable]
  167 |         int cnt=0;
      |             ^~~
bottle.cpp:274:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  274 |         while (idx<vec.size()&&vec[idx].first==i) {
      |                ~~~^~~~~~~~~~~
bottle.cpp:146:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |     scanf("%d %d %d %d",&n,&m,&pp,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:148:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |         scanf("%s",arr[i]);
      |         ~~~~~^~~~~~~~~~~~~
bottle.cpp:151:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |         scanf("%d %d",&xp[i],&yp[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:156:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |         scanf("%d %d",&s[i],&t[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 95 ms 175692 KB Output is correct
2 Correct 89 ms 176172 KB Output is correct
3 Correct 92 ms 177436 KB Output is correct
4 Correct 320 ms 183448 KB Output is correct
5 Correct 329 ms 183560 KB Output is correct
6 Correct 348 ms 183144 KB Output is correct
7 Correct 316 ms 183772 KB Output is correct
8 Correct 317 ms 184720 KB Output is correct
9 Correct 235 ms 184968 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 196 ms 189476 KB Output is correct
2 Correct 325 ms 195892 KB Output is correct
3 Correct 2524 ms 374544 KB Output is correct
4 Correct 2666 ms 372552 KB Output is correct
5 Correct 2749 ms 380116 KB Output is correct
6 Correct 1805 ms 367584 KB Output is correct
7 Correct 2661 ms 370696 KB Output is correct
8 Correct 2790 ms 380368 KB Output is correct
9 Correct 2823 ms 381508 KB Output is correct
10 Correct 2593 ms 377296 KB Output is correct
11 Correct 2547 ms 373976 KB Output is correct
12 Correct 1517 ms 511812 KB Output is correct
13 Runtime error 2300 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 187 ms 189608 KB Output is correct
2 Correct 319 ms 196084 KB Output is correct
3 Correct 2233 ms 373816 KB Output is correct
4 Correct 3076 ms 386952 KB Output is correct
5 Correct 2997 ms 393716 KB Output is correct
6 Correct 3036 ms 392936 KB Output is correct
7 Correct 2709 ms 391792 KB Output is correct
8 Correct 2958 ms 395036 KB Output is correct
9 Runtime error 1873 ms 524288 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3252 ms 384168 KB Output is correct
2 Correct 4124 ms 392136 KB Output is correct
3 Correct 2715 ms 383116 KB Output is correct
4 Correct 4581 ms 399472 KB Output is correct
5 Correct 4897 ms 404060 KB Output is correct
6 Correct 3679 ms 398296 KB Output is correct
7 Correct 2827 ms 384612 KB Output is correct
8 Runtime error 1942 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -