| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 594927 |
2022-07-13T07:16:26 Z |
조영욱(#8439) |
물병 (JOI14_bottle) |
C++14 |
|
5000 ms |
241744 KB |
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
int n,m,pp,q;
typedef pair<int,int> P;
char arr[2000][2001];
int xp[200000];
int yp[200000];
int s[200000];
int t[200000];
int lo[200000]; //�Ұ���
int hi[200000]; //����
int mid[200000];
int dist[4001][4001];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int p[16200000];
vector<int> vec[4100000];
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];
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*m)/2+10;i++) {
vec[i].clear();
}
for(int i=0;i<q;i++) {
mid[i]=(((lo[i]/2)+(hi[i]/2))/2)*2;
if (lo[i]+2!=hi[i]) {
flag=false;
vec[mid[i]/2].push_back(i);
cnt++;
}
}
if (flag) {
break;
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
dist[i][j]=-1;
}
}
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;cnt;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];
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 j=0;j<vec[i].size();j++) {
cnt--;
int one=s[vec[i][j]];
int two=t[vec[i][j]];
if (find(xp[one]*m+yp[one])==find(xp[two]*m+yp[two])) {
hi[vec[i][j]]=mid[vec[i][j]];
}
else {
lo[vec[i][j]]=mid[vec[i][j]];
}
}
}
}
for(int i=0;i<(n*m)/2+10;i++) {
vec[i].clear();
}
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[((lo[i]+hi[i])/2)/2].push_back(i);
cnt++;
}
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;
}
}
}
for(int i=0;cnt;i++) {
for(int j=0;j<vec[i].size();j++) {
int one=s[vec[i][j]];
int two=t[vec[i][j]];
cnt--;
if (find((2*xp[one]+1)*len+(2*yp[one]+1))==find((2*xp[two]+1)*len+(2*yp[two]+1))) {
ret[vec[i][j]]=2*i+1;
}
else {
ret[vec[i][j]]=2*i+2;
}
}
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 main()':
bottle.cpp:120:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for(int j=0;j<vec[i].size();j++) {
| ~^~~~~~~~~~~~~~
bottle.cpp:162:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | for(int j=0;j<vec[i].size();j++) {
| ~^~~~~~~~~~~~~~
bottle.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | scanf("%d %d %d %d",&n,&m,&pp,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
53 | scanf("%s",arr[i]);
| ~~~~~^~~~~~~~~~~~~
bottle.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d %d",&xp[i],&yp[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | scanf("%d %d",&s[i],&t[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
223052 KB |
Output is correct |
| 2 |
Correct |
117 ms |
223264 KB |
Output is correct |
| 3 |
Correct |
139 ms |
223224 KB |
Output is correct |
| 4 |
Correct |
282 ms |
240764 KB |
Output is correct |
| 5 |
Correct |
284 ms |
240316 KB |
Output is correct |
| 6 |
Correct |
281 ms |
241076 KB |
Output is correct |
| 7 |
Correct |
271 ms |
241744 KB |
Output is correct |
| 8 |
Correct |
281 ms |
241280 KB |
Output is correct |
| 9 |
Correct |
276 ms |
240984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
317 ms |
226892 KB |
Output is correct |
| 2 |
Correct |
605 ms |
223796 KB |
Output is correct |
| 3 |
Execution timed out |
5101 ms |
140648 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
378 ms |
226872 KB |
Output is correct |
| 2 |
Correct |
545 ms |
223452 KB |
Output is correct |
| 3 |
Execution timed out |
5068 ms |
228372 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5058 ms |
156656 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
