oj.uz

답안 #5705

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
5705 2014-05-14T04:55:08 Z cki86201 물병 (JOI14_bottle) C++
100 / 100
 1576 ms 144372 KB 
#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>=0;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
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 138124 KB Output is correct
2 Correct 8 ms 138124 KB Output is correct
3 Correct 20 ms 138128 KB Output is correct
4 Correct 100 ms 138132 KB Output is correct
5 Correct 116 ms 138132 KB Output is correct
6 Correct 104 ms 138128 KB Output is correct
7 Correct 96 ms 138124 KB Output is correct
8 Correct 108 ms 138128 KB Output is correct
9 Correct 100 ms 138132 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 138132 KB Output is correct
2 Correct 52 ms 138144 KB Output is correct
3 Correct 420 ms 138136 KB Output is correct
4 Correct 628 ms 138132 KB Output is correct
5 Correct 700 ms 138140 KB Output is correct
6 Correct 424 ms 138136 KB Output is correct
7 Correct 640 ms 138140 KB Output is correct
8 Correct 684 ms 138144 KB Output is correct
9 Correct 804 ms 138140 KB Output is correct
10 Correct 480 ms 138124 KB Output is correct
11 Correct 556 ms 138132 KB Output is correct
12 Correct 184 ms 138136 KB Output is correct
13 Correct 296 ms 138280 KB Output is correct
14 Correct 180 ms 138140 KB Output is correct
15 Correct 296 ms 138276 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 138132 KB Output is correct
2 Correct 44 ms 138132 KB Output is correct
3 Correct 332 ms 138124 KB Output is correct
4 Correct 624 ms 138140 KB Output is correct
5 Correct 688 ms 138140 KB Output is correct
6 Correct 832 ms 138136 KB Output is correct
7 Correct 492 ms 138124 KB Output is correct
8 Correct 604 ms 138140 KB Output is correct
9 Correct 180 ms 138152 KB Output is correct
10 Correct 276 ms 138284 KB Output is correct
11 Correct 268 ms 138240 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 540 ms 138136 KB Output is correct
2 Correct 1080 ms 138244 KB Output is correct
3 Correct 500 ms 138128 KB Output is correct
4 Correct 1432 ms 138224 KB Output is correct
5 Correct 1576 ms 138212 KB Output is correct
6 Correct 856 ms 138160 KB Output is correct
7 Correct 488 ms 138128 KB Output is correct
8 Correct 180 ms 138132 KB Output is correct
9 Correct 1264 ms 138204 KB Output is correct
10 Correct 1012 ms 144372 KB Output is correct
11 Correct 1268 ms 141956 KB Output is correct
12 Correct 1092 ms 143464 KB Output is correct