Submission #594956

# Submission time Handle Problem Language Result Execution time Memory
594956 2022-07-13T07:48:50 Z 조영욱(#8439) 물병 (JOI14_bottle) C++14
0 / 100
5000 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[4001]; //64
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
vector<int> p; //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];
int sst[4000000];
int ss=0;
int f=0;
int top[4000000]; //16
int ind[4000000]; //16
int par[4000000]; //16
int chk=0;

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;
    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)) {
                            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.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)) {
                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);
        memset(seg,0,sizeof(seg));
        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]);
                }
            }
        }
        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;
    }
    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 'int query(int, int)':
bottle.cpp:102:5: warning: unused variable 'cnt' [-Wunused-variable]
  102 | int cnt=0;
      |     ^~~
bottle.cpp: In function 'int main()':
bottle.cpp:165:14: warning: unused variable 'flag' [-Wunused-variable]
  165 |         bool flag=true;
      |              ^~~~
bottle.cpp:166:13: warning: unused variable 'cnt' [-Wunused-variable]
  166 |         int cnt=0;
      |             ^~~
bottle.cpp:254:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  254 |         for(int j=0;j<dist[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~~
bottle.cpp:259:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  259 |     for(int i=0;i<p.size();i++) {
      |                 ~^~~~~~~~~
bottle.cpp:288: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]
  288 |         while (idx<vec.size()&&vec[idx].first==i) {
      |                ~~~^~~~~~~~~~~
bottle.cpp:145:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |     scanf("%d %d %d %d",&n,&m,&pp,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:147:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         scanf("%s",arr[i]);
      |         ~~~~~^~~~~~~~~~~~~
bottle.cpp:150:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |         scanf("%d %d",&xp[i],&yp[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:155:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         scanf("%d %d",&s[i],&t[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 61 ms 65816 KB Output is correct
2 Correct 73 ms 66336 KB Output is correct
3 Correct 95 ms 68460 KB Output is correct
4 Execution timed out 5017 ms 71668 KB Time limit exceeded
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 138 ms 85616 KB Output is correct
2 Correct 298 ms 98832 KB Output is correct
3 Correct 2870 ms 402044 KB Output is correct
4 Correct 2874 ms 400256 KB Output is correct
5 Correct 3145 ms 402208 KB Output is correct
6 Correct 2004 ms 402412 KB Output is correct
7 Correct 2954 ms 400276 KB Output is correct
8 Correct 3210 ms 402368 KB Output is correct
9 Correct 3115 ms 401532 KB Output is correct
10 Correct 2944 ms 404548 KB Output is correct
11 Correct 2902 ms 404500 KB Output is correct
12 Runtime error 1649 ms 524288 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 324 ms 85580 KB Output is correct
2 Correct 473 ms 98968 KB Output is correct
3 Execution timed out 5073 ms 292568 KB Time limit exceeded
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 5022 ms 295380 KB Time limit exceeded
2 Halted 0 ms 0 KB -