oj.uz

Submission #43356

# Submission time Handle Problem Language Result Execution time Memory
43356 2018-03-14T06:31:05 Z ffresh 물병 (JOI14_bottle) C++14
100 / 100
 1454 ms 95684 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5624 KB Output is correct
2 Correct 10 ms 6880 KB Output is correct
3 Correct 11 ms 7060 KB Output is correct
4 Correct 99 ms 7844 KB Output is correct
5 Correct 98 ms 7844 KB Output is correct
6 Correct 100 ms 7868 KB Output is correct
7 Correct 97 ms 7960 KB Output is correct
8 Correct 103 ms 8320 KB Output is correct
9 Correct 165 ms 8320 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 23432 KB Output is correct
2 Correct 51 ms 23432 KB Output is correct
3 Correct 469 ms 38368 KB Output is correct
4 Correct 577 ms 39588 KB Output is correct
5 Correct 620 ms 41616 KB Output is correct
6 Correct 476 ms 41616 KB Output is correct
7 Correct 593 ms 41616 KB Output is correct
8 Correct 656 ms 41616 KB Output is correct
9 Correct 636 ms 44648 KB Output is correct
10 Correct 424 ms 44648 KB Output is correct
11 Correct 447 ms 44648 KB Output is correct
12 Correct 265 ms 44648 KB Output is correct
13 Correct 328 ms 44648 KB Output is correct
14 Correct 249 ms 44648 KB Output is correct
15 Correct 319 ms 44648 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 44648 KB Output is correct
2 Correct 41 ms 44648 KB Output is correct
3 Correct 360 ms 44648 KB Output is correct
4 Correct 542 ms 44648 KB Output is correct
5 Correct 561 ms 44648 KB Output is correct
6 Correct 620 ms 44740 KB Output is correct
7 Correct 409 ms 44740 KB Output is correct
8 Correct 515 ms 44740 KB Output is correct
9 Correct 281 ms 44740 KB Output is correct
10 Correct 345 ms 44740 KB Output is correct
11 Correct 324 ms 44740 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 44740 KB Output is correct
2 Correct 1033 ms 83736 KB Output is correct
3 Correct 408 ms 83736 KB Output is correct
4 Correct 1280 ms 87984 KB Output is correct
5 Correct 1454 ms 93304 KB Output is correct
6 Correct 719 ms 93304 KB Output is correct
7 Correct 403 ms 93304 KB Output is correct
8 Correct 219 ms 93304 KB Output is correct
9 Correct 1327 ms 95684 KB Output is correct
10 Correct 1096 ms 95684 KB Output is correct
11 Correct 1310 ms 95684 KB Output is correct
12 Correct 1203 ms 95684 KB Output is correct