답안 #594981

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
594981 2022-07-13T08:26:39 Z 조영욱(#8439) 물병 (JOI14_bottle) C++14
100 / 100
4696 ms 503476 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
typedef pair<P,int> Pi;
Pi edge[8000000]; //96
int big=4000000;
int st[4000000]; //16
int ss=0;
int f=0;
int ind[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) {
    p[v+big]=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;
        }
        p[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],p[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]) {
            p[nt+big*2]=p[v+big*2];
            dfs_hld(nt);
        }
        else {
            p[nt+big*2]=nt;
            dfs_hld(nt);
        }
    }
}

int query(int u,int v) {
int cnt=0;
    int ret=0;
    while (1) {
        if (p[u+big*2]==p[v+big*2]) {
            break;
        }
        if (ind[p[u+big*2]]>ind[p[v+big*2]]) {
            ret=max(ret,sum(ind[p[u+big*2]],ind[u]));
            u=p[p[u+big*2]+big];
        }
        else {
            ret=max(ret,sum(ind[p[v+big*2]],ind[v]));
            v=p[p[v+big*2]+big];
        }
    }
    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);
        p[big*2]=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:101:5: warning: unused variable 'cnt' [-Wunused-variable]
  101 | int cnt=0;
      |     ^~~
bottle.cpp: In function 'int main()':
bottle.cpp:164:14: warning: unused variable 'flag' [-Wunused-variable]
  164 |         bool flag=true;
      |              ^~~~
bottle.cpp:165:13: warning: unused variable 'cnt' [-Wunused-variable]
  165 |         int cnt=0;
      |             ^~~
bottle.cpp:272: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]
  272 |         while (idx<vec.size()&&vec[idx].first==i) {
      |                ~~~^~~~~~~~~~~
bottle.cpp:144:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |     scanf("%d %d %d %d",&n,&m,&pp,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:146:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |         scanf("%s",arr[i]);
      |         ~~~~~^~~~~~~~~~~~~
bottle.cpp:149:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |         scanf("%d %d",&xp[i],&yp[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:154:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |         scanf("%d %d",&s[i],&t[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 175528 KB Output is correct
2 Correct 93 ms 176032 KB Output is correct
3 Correct 94 ms 176944 KB Output is correct
4 Correct 347 ms 183052 KB Output is correct
5 Correct 313 ms 183096 KB Output is correct
6 Correct 361 ms 182828 KB Output is correct
7 Correct 333 ms 183480 KB Output is correct
8 Correct 309 ms 184144 KB Output is correct
9 Correct 224 ms 184696 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 189 ms 187292 KB Output is correct
2 Correct 302 ms 191320 KB Output is correct
3 Correct 2511 ms 328008 KB Output is correct
4 Correct 2681 ms 326048 KB Output is correct
5 Correct 2739 ms 333272 KB Output is correct
6 Correct 1821 ms 320716 KB Output is correct
7 Correct 2575 ms 323988 KB Output is correct
8 Correct 2756 ms 333480 KB Output is correct
9 Correct 2780 ms 334840 KB Output is correct
10 Correct 2558 ms 330364 KB Output is correct
11 Correct 2523 ms 327164 KB Output is correct
12 Correct 1489 ms 462688 KB Output is correct
13 Correct 2520 ms 481820 KB Output is correct
14 Correct 1804 ms 482148 KB Output is correct
15 Correct 2292 ms 481956 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 181 ms 187396 KB Output is correct
2 Correct 295 ms 191780 KB Output is correct
3 Correct 2252 ms 327528 KB Output is correct
4 Correct 3004 ms 340708 KB Output is correct
5 Correct 3044 ms 347124 KB Output is correct
6 Correct 3108 ms 346472 KB Output is correct
7 Correct 2812 ms 345200 KB Output is correct
8 Correct 2986 ms 348464 KB Output is correct
9 Correct 1848 ms 482624 KB Output is correct
10 Correct 2266 ms 482520 KB Output is correct
11 Correct 2169 ms 496328 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3295 ms 337916 KB Output is correct
2 Correct 4086 ms 346100 KB Output is correct
3 Correct 2768 ms 336836 KB Output is correct
4 Correct 4646 ms 353764 KB Output is correct
5 Correct 4696 ms 357860 KB Output is correct
6 Correct 3910 ms 352156 KB Output is correct
7 Correct 2691 ms 338404 KB Output is correct
8 Correct 1668 ms 481888 KB Output is correct
9 Correct 3891 ms 431044 KB Output is correct
10 Correct 3048 ms 503476 KB Output is correct
11 Correct 3768 ms 434744 KB Output is correct
12 Correct 3151 ms 462652 KB Output is correct