제출 #5704

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
5704		cki86201	물병 (JOI14_bottle)	C++98	30 / 100	808 ms	138284 KiB

bottle

#include<stdio.h>
#include<algorithm>
using namespace std;

#define X first
#define Y second
typedef pair<int,int> Pi;

int H, W, P, Q;
char ch[2020][2020];
Pi inp[200020];
int Que[2002*2002];
int wh[2002*2002], di[2002*2002];
Pi vec[2002*2002];
int topv;
bool chk[2002*2002];
int xx[4] = {0, 1, 0, -1}, yy[4] = {1, 0, -1, 0};
int st[200020], en[400040], nxt[400040], len[400040];
inline void addE(int s,int e,int c,int l){nxt[c]=st[s],st[s]=c,en[c]=e,len[c]=l;}
inline void add(int s,int e,int &c,int l){addE(s,e,++c,l);addE(e,s,++c,l);}
struct edge{
	edge(){}
	edge(int s,int e,int l):s(s),e(e),l(l){}
	int s, e, l;
	bool operator<(const edge &a)const{
		return l<a.l;
	}
}E[1000010];
int top;

struct unf{
	static const int N_ = 200020;
	unf(){for(int i=0;i<N_;i++)p[i] = i, w[i] = 1;}
	int p[N_], w[N_];
	int Find(int x){
		if(p[x] == x)return x;
		return p[x] = Find(p[x]);
	}
	bool Union(int x,int y){
		x = Find(x), y = Find(y);
		if(x == y)return false;
		if(w[x] > w[y])w[x] += w[y], p[y] = x;
		else w[y] += w[x], p[x] = y;
		return true;
	}
	bool chk(int x,int y){return Find(x) == Find(y);}
}uf;

int up[200020][18];
int mx[200020][18];
int dep[200020];
bool vis[200020];

void dfs(int x)
{
	vis[x] = 1;
	for(int i=st[x];i;i=nxt[i])
		if(!vis[en[i]]){
			dep[en[i]] = dep[x] + 1;
			up[en[i]][0] = x;
			mx[en[i]][0] = len[i];
			for(int j=1;j<18;j++){
				up[en[i]][j] = up[ up[en[i]][j-1] ][j-1];
				mx[en[i]][j] = max(mx[en[i]][j-1], mx[up[en[i]][j-1]][j-1]);
			}
			dfs(en[i]);
		}
}

int Get(int x,int y)
{
	if(dep[x] < dep[y])swap(x,y);
	int res = 0;
	for(int i=0;i<18;i++){
		if(1<<i&(dep[x]-dep[y]))res = max(res, mx[x][i]), x = up[x][i];
	}
	if(x == y)return res;
	for(int i=17;i;i--)
		if(up[x][i] != up[y][i]){
			res = max(res, mx[x][i]);
			res = max(res, mx[y][i]);
			x = up[x][i], y = up[y][i];
		}
	return max(res, max(mx[y][0], mx[x][0]));
}

int main()
{
	scanf("%d%d%d%d",&H,&W,&P,&Q);
	int i;
	for(i=0;i<H;i++)scanf("%s",ch[i]);
	int *fr = Que, *re = Que;
	for(i=1;i<=P;i++){
		scanf("%d%d",&inp[i].X,&inp[i].Y);
		--inp[i].X; --inp[i].Y;
		int a = inp[i].X * W + inp[i].Y;
		*fr++ = a; wh[a] = i; chk[a] = 1;
	}
	int now = 0;
	while(fr != re){
		int t = *re++;
		if(di[t] != now){
			now = di[t];
			while(topv--)uf.Union(vec[topv].X, vec[topv].Y);
			topv = 0;
		}
		for(i=0;i<4;i++){
			int tx = t/W + xx[i];
			int ty = t%W + yy[i];
			if(tx < 0 || tx >= H || ty < 0 || ty >= W || ch[tx][ty] == '#')continue;
			int nex = tx*W+ty;
			if(!chk[nex]){
				*fr++ = nex;
				di[nex] = di[t] + 1;
				wh[nex] = wh[t];
				chk[nex] = 1;
			}
			if(chk[nex] && uf.chk(wh[nex], wh[t]))continue;
			if(chk[nex])E[top++] = edge(wh[nex], wh[t], di[t] + di[nex]), vec[topv++] = Pi(wh[nex], wh[t]);
		}
	}
	sort(E, E+top);
	uf = unf();
	int c_edge = 2;
	for(i=0;i<top;i++)if(uf.Union(E[i].s, E[i].e))add(E[i].s, E[i].e, c_edge, E[i].l);
	for(i=1;i<=P;i++)if(!vis[i])dfs(i);
	for(int tt=1;tt<=Q;tt++){
		int x, y;
		scanf("%d%d",&x,&y);
		if(!uf.chk(x,y))printf("-1\n");
		else printf("%d\n",Get(x,y));
	}
	return 0;
}

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