oj.uz

답안 #5804

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
5804 2014-05-17T10:40:18 Z ainta 물병 (JOI14_bottle) C++
100 / 100
 1500 ms 165296 KB 
#include<stdio.h>
#include<algorithm>
#include<vector>
#define W_ 2010
#define N_ 200010
#define INF 999999999
using namespace std;
int H, W, n, Query, D[W_][W_], P[W_][W_], Q[W_*W_], h, t, par[N_];
int pp[18][N_], LL[18][N_], Dep[N_];
vector<int>E[N_], L[N_];
struct Edge{
	int a, b, d;
	bool operator <(const Edge &p)const{
		return d<p.d;
	}
}tp;
vector<Edge>Ed;
char p[W_][W_];
void Do(int x, int y, int d, int pv){
	if (P[x][y] && pv != P[x][y]){
		tp.a = pv, tp.b = P[x][y], tp.d = d + D[x][y] - 1;
		Ed.push_back(tp);
	}
	if (p[x][y] == '.' && D[x][y] > d){
		P[x][y] = pv, D[x][y] = d;
		Q[++t] = x*(W + 1) + y;
	}
}
void BFS(int x, int y)
{
	Do(x - 1, y, D[x][y] + 1, P[x][y]);
	Do(x + 1, y, D[x][y] + 1, P[x][y]);
	Do(x, y - 1, D[x][y] + 1, P[x][y]);
	Do(x, y + 1, D[x][y] + 1, P[x][y]);
}
int find(int a){
	if (a == par[a])return a;
	return par[a] = find(par[a]);
}
void Connect(int a, int b, int d)
{
	int x = find(a), y = find(b);
	if (x == y)return;
	E[a].push_back(b); L[a].push_back(d);
	E[b].push_back(a); L[b].push_back(d);
	par[x] = y;
}
void DFS(int a, int pa){
	Dep[a] = Dep[pa] + 1;
	pp[0][a] = pa;
	int i;
	for (i = 0; i < E[a].size(); i++){
		if (E[a][i] != pa){
			DFS(E[a][i], a);
			LL[0][E[a][i]] = L[a][i];
		}
	}
}
int Gap(int x, int y)
{
	if (Dep[x] < Dep[y])return Gap(y, x);
	int d = Dep[x] - Dep[y], c = 0, r = 0, i;
	while (d){
		if (d & 1){
			r = max(r, LL[c][x]);
			x = pp[c][x];
		}
		c++;
		d >>= 1;
	}
	for (i = 17; i >= 0; i--){
		if (pp[i][x] != pp[i][y]){
			r = max(r, max(LL[i][x], LL[i][y]));
			x = pp[i][x], y = pp[i][y];
		}
	}
	if (x != y){
		r = max(r, max(LL[0][x], LL[0][y]));
		x = pp[0][x], y = pp[0][y];
	}
	if (!x)return -1;
	return r;
}
int main()
{
	int i, j, x, y;
	scanf("%d%d%d%d", &H, &W, &n, &Query);
	for (i = 1; i <= H; i++){
		scanf("%s", p[i] + 1);
		for (j = 1; j <= W; j++){
			D[i][j] = INF;
		}
	}
	for (i = 1; i <= n; i++){
		scanf("%d%d", &x, &y);
		Q[++t] = x*(W + 1) + y;
		D[x][y] = 0, P[x][y] = i;
		par[i] = i;
	}
	while (h < t){
		++h;
		BFS(Q[h] / (W + 1), Q[h] % (W + 1));
	}
	sort(Ed.begin(), Ed.end());
	for (i = 0; i != Ed.size(); i++){
		Connect(Ed[i].a, Ed[i].b, Ed[i].d);
	}
	for (i = 1; i <= n; i++){
		if (!pp[0][i])DFS(i, 0);
	}
	for (i = 1; i < 18; i++){
		for (j = 1; j <= n; j++){
			pp[i][j] = pp[i - 1][pp[i - 1][j]];
			LL[i][j] = max(LL[i - 1][j], LL[i - 1][pp[i - 1][j]]);
		}
	}
	while (Query--)
	{
		scanf("%d%d", &x, &y);
		printf("%d\n", Gap(x, y));
	}
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 91564 KB Output is correct
2 Correct 0 ms 91756 KB Output is correct
3 Correct 0 ms 91564 KB Output is correct
4 Correct 92 ms 91564 KB Output is correct
5 Correct 96 ms 91756 KB Output is correct
6 Correct 96 ms 91564 KB Output is correct
7 Correct 88 ms 91564 KB Output is correct
8 Correct 96 ms 91948 KB Output is correct
9 Correct 92 ms 91564 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 92144 KB Output is correct
2 Correct 36 ms 93872 KB Output is correct
3 Correct 360 ms 92720 KB Output is correct
4 Correct 464 ms 96176 KB Output is correct
5 Correct 508 ms 100784 KB Output is correct
6 Correct 348 ms 92720 KB Output is correct
7 Correct 476 ms 96176 KB Output is correct
8 Correct 516 ms 100784 KB Output is correct
9 Correct 576 ms 110000 KB Output is correct
10 Correct 360 ms 93872 KB Output is correct
11 Correct 428 ms 96176 KB Output is correct
12 Correct 152 ms 96176 KB Output is correct
13 Correct 248 ms 92780 KB Output is correct
14 Correct 136 ms 96176 KB Output is correct
15 Correct 244 ms 92780 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 92144 KB Output is correct
2 Correct 32 ms 92144 KB Output is correct
3 Correct 256 ms 91756 KB Output is correct
4 Correct 496 ms 96176 KB Output is correct
5 Correct 520 ms 100784 KB Output is correct
6 Correct 592 ms 110000 KB Output is correct
7 Correct 400 ms 93872 KB Output is correct
8 Correct 468 ms 96176 KB Output is correct
9 Correct 168 ms 96176 KB Output is correct
10 Correct 272 ms 92780 KB Output is correct
11 Correct 256 ms 92132 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 480 ms 92732 KB Output is correct
2 Correct 1152 ms 115416 KB Output is correct
3 Correct 384 ms 93872 KB Output is correct
4 Correct 1336 ms 128500 KB Output is correct
5 Correct 1500 ms 165296 KB Output is correct
6 Correct 680 ms 100784 KB Output is correct
7 Correct 364 ms 93872 KB Output is correct
8 Correct 108 ms 92720 KB Output is correct
9 Correct 1300 ms 165296 KB Output is correct
10 Correct 1048 ms 122492 KB Output is correct
11 Correct 1296 ms 165296 KB Output is correct
12 Correct 1140 ms 139112 KB Output is correct