Submission #43354

#	Time	Username	Problem	Language	Result	Execution time	Memory
43354		ffresh	물병 (JOI14_bottle)	C++14	0 / 100	401 ms	34752 KiB

bottle

#include <bits/stdc++.h>
using namespace std;

const int N = 2005,M = 2e5+15,T = 20;

int color[N][N];

int py[M],px[M];

vector<pair<int,int> >adj[N];

int par[M];

int f(int x){
	if(x==par[x])return x;
	return par[x]= f(par[x]);
}
bool vis[M];

int dy[4]= {1,-1,0,0},dx[4]= {0,0,1,-1};

int dist(int id,int y,int x){
	return abs(py[id]-y)+ abs(px[id]-x);
}

int depth[M],lca[M][T],value[M][T];

void dfs(int root,int p){
	depth[root]= depth[p]+1;
	vis[root]= 1;
	
    for(int i=1;i<T;++i){
		lca[root][i]= lca[lca[root][i-1]][i-1];
		value[root][i]= max(value[root][i-1], value[lca[root][i-1]][i-1]);
	}

	for(int i=0;i<adj[root].size();++i){
		int u = adj[root][i].second;

		int m = adj[root][i].first;

        
		if(u==p)continue;

		lca[u][0]= root;
		value[u][0]= m;

		dfs(u,root);
	}
}

int getvalue(int x,int y){
	if(depth[x]<depth[y])swap(x,y);
	int D= depth[x]-depth[y];
	int val = 0;
	for(int i=0;i<T;++i){
		if(D&(1<<i)){

			val= max(val, value[x][i]);
			x = lca[x][i];
		}
	}

	if(x!=y){

		for(int i=T-1;i>=0;--i){

			if(lca[x][i]!= lca[y][i]){
				val = max(val,value[x][i]);
				val = max(val,value[y][i]);
				x = lca[x][i],y = lca[y][i];
			}
		}
		val = max(val,max(value[x][0],value[y][0]));
	}

	return val;
}
int main(){
	//freopen("input.txt","r",stdin);

	int h,w,p,q;

	cin>>h>>w>>p>>q;

	for(int i=1;i<=h;++i){
		string s;cin>>s;
		for(int j=1;j<=w;++j){
			if(s[j-1]=='#'){
				color[i][j]= -1;
			}
		}
	}
	int y,x;

	queue<pair<pair<int,int>,int>  >qq,temp;

	for(int i=1;i<=p;++i)
	{	
		par[i]= i;
		scanf("%d%d",&py[i],&px[i]);
		color[py[i]][px[i]]= i;
		qq.push(make_pair(make_pair(py[i],px[i]),i ));
	}	

	while(!qq.empty()){
		


		while(!qq.empty()){
			int id= qq.front().second, y = qq.front().first.first, x = qq.front().first.second;

			
			qq.pop();
			
			for(int j=0;j<4;++j){
				int ny = dy[j]+ y, nx = dx[j] + x;

				if(ny>0 && ny<=h && nx>0 && nx<=w && color[ny][nx]==0){
					color[ny][nx]= id;
					temp.push(make_pair(make_pair(ny,nx),id));
				}			
			}
		}	
		swap(qq,temp);
	}

	vector<pair<int,pair<int,int> > >Edge;

	for(int i=1;i<=h;++i){
		for(int j=1;j<=w;++j){

			if(color[i][j]!=-1){
				int id = color[i][j];

				int id2= color[i][j+1];

				if(j+1<=w && id2!=id && id2!=-1 ){
					Edge.push_back(make_pair(dist(id,i,j)+ dist(id2,i,j+1),make_pair(id,id2)));
				}
				id2 = color[i+1][j];
				if(i+1<= h && id2!=id && id2!=-1){
					Edge.push_back(make_pair(dist(id,i,j)+ dist(id2,i+1,j),make_pair(id,id2)));
				}
			}
		}
	}

	sort(Edge.begin(),Edge.end());

	for(int i=0;i<(int)Edge.size();++i){

		int a = Edge[i].second.first, b = Edge[i].second.second;
		
		if(f(a)!=f(b)){
			par[f(b)]= f(a);
            //cout<<a<<" "<<b<<" "<<Edge[i].first<<endl;
			adj[a].push_back(make_pair(Edge[i].first,b));
			adj[b].push_back(make_pair(Edge[i].first,a));
		}
	}
	
	for(int i=1;i<=p;++i){
		if(!vis[i]){
			dfs(i,0);
		}
	}
	while(q--){
		scanf("%d%d",&x,&y);

		if(f(x)!=f(y)){
			printf("-1\n");
		}
		else{
			printf("%d\n",getvalue(x,y));
		}
	}
}

Compilation message (stderr)

bottle.cpp: In function 'void dfs(int, int)':
bottle.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[root].size();++i){
               ^
bottle.cpp: In function 'int main()':
bottle.cpp:101:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&py[i],&px[i]);
                              ^
bottle.cpp:169:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
                      ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30