답안 #594931

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
594931 2022-07-13T07:22:12 Z 조영욱(#8439) 물병 (JOI14_bottle) C++14
10 / 100
1756 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
vector<int> dist[4000];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
vector<int> p;
vector<P> vec;
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
vector<P> adj[4000000]; //256
vector<int> son[4000000]; //64
int f=0;
int top[4000000];
int ind[4000000];
int sz[4000000];
int dep[4000000];
int par[4000000];

const int siz=(1<<23);
int seg[siz*2];

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;
    sz[v]=1;
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i].first;
        if (nt==prev) {
            continue;
        }
        val[nt]=adj[v][i].second;
        son[v].push_back(nt);
        dep[nt]=dep[v]+1;
        dfs_sz(nt,v);
        sz[v]+=sz[nt];
        if (sz[nt]>sz[son[v][0]]) {
            swap(son[v][0],son[v][son[v].size()-1]);
        }
    }
}

void dfs_hld(int v) {
    ind[v]=f++;
    update(ind[v],val[v]);
    for(int i=0;i<son[v].size();i++) {
        int nt=son[v][i];
        if (i==0) {
            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 (dep[top[u]]>dep[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 (dep[u]<dep[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;
    }
    while (1) {
        bool flag=true;
        int cnt=0;
        for(int i=0;i<n;i++){
            dist[i].resize(m);
        for(int j=0;j<m;j++) {
            dist[i][j]=-1;
        }
        }
        p.resize(n*m);
        for(int i=0;i<n*m;i++) {
            p[i]=-1;
        }
        queue<P> que;
        for(int i=0;i<pp;i++) {
            que.push(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 (!que.empty()) {
                P now=que.front();
                if (dist[now.first][now.second]>=i) {
                    break;
                }
                que.pop();
                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)) {
                            adj[x*m+y].push_back(P(nt,i));
                            adj[nt].push_back(P(x*m+y,i));
                            merge(x*m+y,nt);
                        }
                        if (dist[x+dx[j]][y+dy[j]]==-1) {
                            que.push(P(x+dx[j],y+dy[j]));
                            dist[x+dx[j]][y+dy[j]]=dist[x][y]+1;
                        }
                    }
                }
            }
        }
        for(int i=0;i+1<n*m;i++) {
            if (find(i)!=find(i+1)) {
                adj[i].push_back(P(i+1,((n*m)/2+1)));
                adj[i+1].push_back(P(i,((n*m)/2+1)));
                merge(i,i+1);
            }
        }
        dfs_sz(0,-1);
        top[0]=0;
        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;
        }
        break;
    }
    for(int i=0;i<=2*n;i++) {
        dist[i].resize(2*m+1);
        for(int j=0;j<dist[i].size();j++) {
            dist[i][j]=-1;
        }
    }
    p.resize((2*n+1)*(2*m+1));
    for(int i=0;i<p.size();i++) {
        p[i]=-1;
    }
    for(int i=0;i<n*m;i++){
        vector<P>().swap(adj[i]);
        vector<int>().swap(son[i]);
    }
    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;
    queue<P> que;
    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.push(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 (!que.empty()) {
            P now=que.front();
            if (dist[now.first][now.second]>i) {
                break;
            }
            que.pop();
            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.push(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.push(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.push(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.push(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 'void dfs_sz(int, int)':
bottle.cpp:61:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
bottle.cpp: In function 'void dfs_hld(int)':
bottle.cpp:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i=0;i<son[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
bottle.cpp: In function 'int query(int, int)':
bottle.cpp:94:5: warning: unused variable 'cnt' [-Wunused-variable]
   94 | int cnt=0;
      |     ^~~
bottle.cpp: In function 'int main()':
bottle.cpp:156:14: warning: unused variable 'flag' [-Wunused-variable]
  156 |         bool flag=true;
      |              ^~~~
bottle.cpp:157:13: warning: unused variable 'cnt' [-Wunused-variable]
  157 |         int cnt=0;
      |             ^~~
bottle.cpp:220:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  220 |         for(int j=0;j<dist[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~~
bottle.cpp:225:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |     for(int i=0;i<p.size();i++) {
      |                 ~^~~~~~~~~
bottle.cpp:258: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]
  258 |         while (idx<vec.size()&&vec[idx].first==i) {
      |                ~~~^~~~~~~~~~~
bottle.cpp:137:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |     scanf("%d %d %d %d",&n,&m,&pp,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:139:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |         scanf("%s",arr[i]);
      |         ~~~~~^~~~~~~~~~~~~
bottle.cpp:142:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         scanf("%d %d",&xp[i],&yp[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:147:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         scanf("%d %d",&s[i],&t[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 189976 KB Output is correct
2 Correct 98 ms 190780 KB Output is correct
3 Correct 111 ms 193828 KB Output is correct
4 Correct 356 ms 199652 KB Output is correct
5 Correct 346 ms 199648 KB Output is correct
6 Correct 390 ms 199592 KB Output is correct
7 Correct 354 ms 200308 KB Output is correct
8 Correct 353 ms 200892 KB Output is correct
9 Correct 239 ms 201568 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 212 ms 217536 KB Output is correct
2 Correct 443 ms 238720 KB Output is correct
3 Runtime error 1745 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 234 ms 217676 KB Output is correct
2 Correct 415 ms 238944 KB Output is correct
3 Runtime error 1466 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1756 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -