Submission #43356

#	Time	Username	Problem	Language	Result	Execution time	Memory
43356		ffresh	물병 (JOI14_bottle)	C++14	100 / 100	1454 ms	95684 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[M];

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 depth[M],lca[M][T],value[M][T],dist[N][N];

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;

	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()){
		
		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;
				dist[ny][nx]= dist[y][x]+1;
				qq.push(make_pair(make_pair(ny,nx),id));
			}			
		}
	}	


	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[i][j]+ dist[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[i][j]+ dist[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:34: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:98: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:163: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: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30