답안 #594971

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
594971 2022-07-13T08:07:41 Z 조영욱(#8439) 물병 (JOI14_bottle) C++14
10 / 100
4763 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
P son[4000000]; //32
int sst[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];
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;
        son[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 (sst[v]==-1) {
        return;
    }
    for(int i=sst[v];i<ss;i++) {
        if (son[i].first!=v) {
            break;
        }
        int nt=son[i].second;
        if (i==sst[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(son,son+ss);
        memset(sst,-1,sizeof(sst));
        for(int i=ss-1;i>=0;i--) {
            sst[son[i].first]=i;
        }
        for(int i=0;i<n*m;i++) {
            if (sst[i]==-1) {
                continue;
            }
            for(int j=sst[i];j<ss;j++) {
                if (son[j].first!=i) {
                    break;
                }
                int pr=sst[i];
                if (seg[son[pr].second]<seg[son[j].second]) {
                    swap(son[pr],son[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:105:5: warning: unused variable 'cnt' [-Wunused-variable]
  105 | int cnt=0;
      |     ^~~
bottle.cpp: In function 'int main()':
bottle.cpp:168:14: warning: unused variable 'flag' [-Wunused-variable]
  168 |         bool flag=true;
      |              ^~~~
bottle.cpp:169:13: warning: unused variable 'cnt' [-Wunused-variable]
  169 |         int cnt=0;
      |             ^~~
bottle.cpp:276: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]
  276 |         while (idx<vec.size()&&vec[idx].first==i) {
      |                ~~~^~~~~~~~~~~
bottle.cpp:148:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |     scanf("%d %d %d %d",&n,&m,&pp,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:150:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |         scanf("%s",arr[i]);
      |         ~~~~~^~~~~~~~~~~~~
bottle.cpp:153:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |         scanf("%d %d",&xp[i],&yp[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:158:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |         scanf("%d %d",&s[i],&t[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 191496 KB Output is correct
2 Correct 109 ms 192032 KB Output is correct
3 Correct 102 ms 193456 KB Output is correct
4 Correct 368 ms 199372 KB Output is correct
5 Correct 338 ms 199428 KB Output is correct
6 Correct 340 ms 199228 KB Output is correct
7 Correct 389 ms 199584 KB Output is correct
8 Correct 323 ms 200548 KB Output is correct
9 Correct 267 ms 200960 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 266 ms 206704 KB Output is correct
2 Correct 341 ms 214700 KB Output is correct
3 Correct 2474 ms 421544 KB Output is correct
4 Correct 2775 ms 419344 KB Output is correct
5 Correct 2948 ms 427044 KB Output is correct
6 Correct 1923 ms 398692 KB Output is correct
7 Correct 2683 ms 417356 KB Output is correct
8 Correct 2822 ms 427228 KB Output is correct
9 Correct 2764 ms 428344 KB Output is correct
10 Correct 2596 ms 424200 KB Output is correct
11 Correct 2536 ms 420952 KB Output is correct
12 Runtime error 1464 ms 524288 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 206 ms 206876 KB Output is correct
2 Correct 305 ms 214900 KB Output is correct
3 Correct 2305 ms 420640 KB Output is correct
4 Correct 3171 ms 433660 KB Output is correct
5 Correct 3069 ms 440656 KB Output is correct
6 Correct 3118 ms 439924 KB Output is correct
7 Correct 2686 ms 438748 KB Output is correct
8 Correct 2971 ms 442108 KB Output is correct
9 Runtime error 1467 ms 524288 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 3215 ms 430948 KB Output is correct
2 Correct 3860 ms 439020 KB Output is correct
3 Correct 2604 ms 430040 KB Output is correct
4 Correct 4354 ms 446428 KB Output is correct
5 Correct 4763 ms 451052 KB Output is correct
6 Correct 3695 ms 445404 KB Output is correct
7 Correct 2854 ms 431716 KB Output is correct
8 Runtime error 1354 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -