답안 #594960

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
594960 2022-07-13T07:54:37 Z 조영욱(#8439) 물병 (JOI14_bottle) C++14
10 / 100
4977 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
vector<int> son[4000000]; //64
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[v].push_back(nt);
        dfs_sz(nt,v);
        seg[v]+=seg[nt];
        if (seg[nt]>seg[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 (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;
    }
    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;
        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<n*m;i++){
        vector<int>().swap(son[i]);
    }
    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 'void dfs_hld(int)':
bottle.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i=0;i<son[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
bottle.cpp: In function 'int query(int, int)':
bottle.cpp:97:5: warning: unused variable 'cnt' [-Wunused-variable]
   97 | int cnt=0;
      |     ^~~
bottle.cpp: In function 'int main()':
bottle.cpp:159:14: warning: unused variable 'flag' [-Wunused-variable]
  159 |         bool flag=true;
      |              ^~~~
bottle.cpp:160:13: warning: unused variable 'cnt' [-Wunused-variable]
  160 |         int cnt=0;
      |             ^~~
bottle.cpp:232:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  232 |         for(int j=0;j<dist[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~~
bottle.cpp:237:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  237 |     for(int i=0;i<p.size();i++) {
      |                 ~^~~~~~~~~
bottle.cpp:266: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]
  266 |         while (idx<vec.size()&&vec[idx].first==i) {
      |                ~~~^~~~~~~~~~~
bottle.cpp:140:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |     scanf("%d %d %d %d",&n,&m,&pp,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:142:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         scanf("%s",arr[i]);
      |         ~~~~~^~~~~~~~~~~~~
bottle.cpp:145:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |         scanf("%d %d",&xp[i],&yp[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",&s[i],&t[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 144076 KB Output is correct
2 Correct 84 ms 144632 KB Output is correct
3 Correct 94 ms 146648 KB Output is correct
4 Correct 381 ms 152260 KB Output is correct
5 Correct 339 ms 153640 KB Output is correct
6 Correct 395 ms 153900 KB Output is correct
7 Correct 331 ms 154272 KB Output is correct
8 Correct 335 ms 155260 KB Output is correct
9 Correct 232 ms 155792 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 222 ms 164136 KB Output is correct
2 Correct 367 ms 177344 KB Output is correct
3 Correct 3090 ms 492448 KB Output is correct
4 Correct 3476 ms 482592 KB Output is correct
5 Correct 3561 ms 486752 KB Output is correct
6 Correct 2334 ms 492836 KB Output is correct
7 Correct 3244 ms 482720 KB Output is correct
8 Correct 3189 ms 487052 KB Output is correct
9 Correct 3354 ms 447620 KB Output is correct
10 Correct 2899 ms 488180 KB Output is correct
11 Correct 2898 ms 488012 KB Output is correct
12 Runtime error 1203 ms 524288 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 202 ms 164232 KB Output is correct
2 Correct 361 ms 177456 KB Output is correct
3 Correct 2643 ms 495308 KB Output is correct
4 Correct 3475 ms 486904 KB Output is correct
5 Correct 3491 ms 491352 KB Output is correct
6 Correct 3844 ms 451620 KB Output is correct
7 Correct 3761 ms 491404 KB Output is correct
8 Correct 3874 ms 493600 KB Output is correct
9 Runtime error 1220 ms 524288 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 4388 ms 494588 KB Output is correct
2 Correct 4836 ms 497120 KB Output is correct
3 Correct 3170 ms 488684 KB Output is correct
4 Correct 4977 ms 489828 KB Output is correct
5 Correct 4965 ms 488176 KB Output is correct
6 Correct 4057 ms 493860 KB Output is correct
7 Correct 2886 ms 493124 KB Output is correct
8 Runtime error 1002 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -