| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 594960 |
2022-07-13T07:54:37 Z |
조영욱(#8439) |
물병 (JOI14_bottle) |
C++14 |
|
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]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
