oj.uz

Submission #15908

# Submission time Handle Problem Language Result Execution time Memory
15908 2015-08-01T07:24:01 Z comet 물병 (JOI14_bottle) C++
100 / 100
 1262 ms 112460 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cassert>
using namespace std;
#define INF (1e9)
struct edge{
	int v,u,c;
	bool operator<(const edge& r)const{
		return c<r.c;
	}
};
struct pt{
	int y,x;
	pt(int y_=0,int x_=0):
		y(y_),x(x_){}
};
struct disjoint{
	vector<int> p;
	disjoint(int n):p(n+1){
		for(int i=1;i<=n;i++)p[i]=i;
	}
	int find(int x){
		if(p[x]==x)return x;
		return p[x]=find(p[x]);
	}
	bool merge(int x,int y){
		x=find(x),y=find(y);
		if(x==y)return 0;
		p[x]=y;
		return 1;
	}
};
int H,W,P;
int dist[2010][2010],area[2010][2010];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int par[200010][20],RMQ[200010][20],in[200010],out[200010],T;
vector<pt> path[200010];
queue<pt> Q;
char a[2010][2010];
void kruskal(vector<edge>& s){
	int n=s.size(),i;
	edge e;
	disjoint alice(P);
	for(i=0;i<n;i++){
		e=s[i];
		if(alice.merge(e.v,e.u)){
			path[e.v].push_back(pt(e.u,e.c));
			path[e.u].push_back(pt(e.v,e.c));
		}
	}
	for(int i=1;i<P;i++){
		if(alice.merge(i,i+1)){
			path[i].push_back(pt(i+1,INF));
			path[i+1].push_back(pt(i,INF));
		}
	}
}
void dfs(int v,int p,int c){
	pt u;
	par[v][0]=p;
	RMQ[v][0]=c;
	in[v]=T++;
	for(int i=1;i<20;i++){
		par[v][i]=par[par[v][i-1]][i-1];
		RMQ[v][i]=max(RMQ[par[v][i-1]][i-1],RMQ[v][i-1]);
	}
	for(int i=0;i<path[v].size();i++){
		u=path[v][i];
		if(u.y==p)continue;
		dfs(u.y,v,u.x);
	}
	out[v]=T++;
}
void init(){
	pt v,u;
	while(!Q.empty()){
		v=Q.front();
		Q.pop();
		for(int i=0;i<4;i++){
			u=pt(v.y+dy[i],v.x+dx[i]);
			if(u.y<=0||u.x<=0||u.y>H||u.x>W)continue;
			if(a[u.y][u.x]=='#')continue;
			if(area[u.y][u.x])continue;
			area[u.y][u.x]=area[v.y][v.x];
			dist[u.y][u.x]=dist[v.y][v.x]+1;
			Q.push(u);
		}
	}
	vector<edge> s;
	for(int i=1;i<=H;i++){
		for(int j=1;j<=W;j++){
			if(i<H&&area[i][j]!=area[i+1][j]&&area[i][j]&&area[i+1][j])
				s.push_back(edge{area[i][j],area[i+1][j],dist[i][j]+dist[i+1][j]});

			if(j<W&&area[i][j]!=area[i][j+1]&&area[i][j]&&area[i][j+1])
				s.push_back(edge{area[i][j],area[i][j+1],dist[i][j]+dist[i][j+1]});

		}
	}
	sort(s.begin(),s.end());
	kruskal(s);
	dfs(1,1,0);
}
bool isParent(int x,int y){
	return in[x]<=in[y]&&out[x]>=out[y];
}
int LCA(int x,int y){
	if(isParent(x,y))return x;
	if(isParent(y,x))return y;
	for(int i=19;i>=0;i--){
		if(!isParent(par[x][i],y))
			x=par[x][i];
	}
	return par[x][0];
}
int f(int p,int v){
	if(p==v)return 0;
	int ret=0;
	for(int i=19;i>=0;i--){
		if(isParent(p,par[v][i])){
			ret=max(ret,RMQ[v][i]);
			v=par[v][i];
		}
	}
	assert(v==p);
	return ret;
}
int query(int x,int y){
	int t=LCA(x,y);
	return max(f(t,x),f(t,y));
}
int main(){
	ios::sync_with_stdio(0);
	int m,x,y,ans;
	cin>>H>>W>>P>>m;
	for(int i=1;i<=H;i++)cin>>&a[i][1];
	for(int i=1;i<=P;i++){
		cin>>y>>x;
		area[y][x]=i;
		Q.push(pt(y,x));
	}
	init();
	while(m--){
		cin>>x>>y;
		ans=query(x,y);
		if(ans>=INF)cout<<"-1"<<endl;
		else cout<<ans<<endl;
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 74864 KB Output is correct
2 Correct 0 ms 74864 KB Output is correct
3 Correct 22 ms 74864 KB Output is correct
4 Correct 522 ms 74864 KB Output is correct
5 Correct 536 ms 74864 KB Output is correct
6 Correct 509 ms 74864 KB Output is correct
7 Correct 553 ms 74864 KB Output is correct
8 Correct 511 ms 75048 KB Output is correct
9 Correct 495 ms 74868 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 75264 KB Output is correct
2 Correct 28 ms 76196 KB Output is correct
3 Correct 216 ms 75620 KB Output is correct
4 Correct 310 ms 77836 KB Output is correct
5 Correct 332 ms 80200 KB Output is correct
6 Correct 211 ms 75620 KB Output is correct
7 Correct 297 ms 77836 KB Output is correct
8 Correct 303 ms 80204 KB Output is correct
9 Correct 330 ms 85408 KB Output is correct
10 Correct 230 ms 76196 KB Output is correct
11 Correct 268 ms 77532 KB Output is correct
12 Correct 102 ms 77528 KB Output is correct
13 Correct 117 ms 75532 KB Output is correct
14 Correct 109 ms 77528 KB Output is correct
15 Correct 122 ms 75532 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 75264 KB Output is correct
2 Correct 44 ms 75284 KB Output is correct
3 Correct 220 ms 74864 KB Output is correct
4 Correct 349 ms 77836 KB Output is correct
5 Correct 345 ms 80200 KB Output is correct
6 Correct 378 ms 85408 KB Output is correct
7 Correct 396 ms 76196 KB Output is correct
8 Correct 307 ms 77836 KB Output is correct
9 Correct 194 ms 77532 KB Output is correct
10 Correct 153 ms 75532 KB Output is correct
11 Correct 148 ms 75092 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 917 ms 75812 KB Output is correct
2 Correct 1103 ms 89100 KB Output is correct
3 Correct 228 ms 76196 KB Output is correct
4 Correct 1129 ms 95240 KB Output is correct
5 Correct 1262 ms 112196 KB Output is correct
6 Correct 1035 ms 80800 KB Output is correct
7 Correct 244 ms 76196 KB Output is correct
8 Correct 124 ms 75528 KB Output is correct
9 Correct 1242 ms 112208 KB Output is correct
10 Correct 966 ms 94256 KB Output is correct
11 Correct 1165 ms 112460 KB Output is correct
12 Correct 1003 ms 102324 KB Output is correct