Submission #15895

#	Time	Username	Problem	Language	Result	Execution time	Memory
15895		comet	물병 (JOI14_bottle)	C++98	0 / 100	692 ms	75808 KiB

bottle

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
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]});

		}
	}
	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];
		}
	}
	//if(v!=p)cout<<"wowowowowo wonderful!!!"<<endl;
	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;
	}
}

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