oj.uz

Submission #5805

# Submission time Handle Problem Language Result Execution time Memory
5805 2014-05-17T11:22:35 Z ainta 물병 (JOI14_bottle) C++
100 / 100
 1516 ms 165296 KB 
#pragma warning(disable:4996)
#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] && (D[x][y] == d - 1 || (D[x][y] == d - 2 && P[x][y] > pv))){
		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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 91564 KB Output is correct
2 Correct 8 ms 91564 KB Output is correct
3 Correct 8 ms 91564 KB Output is correct
4 Correct 96 ms 91564 KB Output is correct
5 Correct 100 ms 91564 KB Output is correct
6 Correct 92 ms 91564 KB Output is correct
7 Correct 96 ms 91564 KB Output is correct
8 Correct 96 ms 91756 KB Output is correct
9 Correct 92 ms 91564 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 91948 KB Output is correct
2 Correct 40 ms 92720 KB Output is correct
3 Correct 376 ms 92144 KB Output is correct
4 Correct 524 ms 96176 KB Output is correct
5 Correct 560 ms 100784 KB Output is correct
6 Correct 360 ms 92144 KB Output is correct
7 Correct 504 ms 96176 KB Output is correct
8 Correct 564 ms 100784 KB Output is correct
9 Correct 628 ms 100784 KB Output is correct
10 Correct 392 ms 92720 KB Output is correct
11 Correct 472 ms 93872 KB Output is correct
12 Correct 160 ms 96176 KB Output is correct
13 Correct 260 ms 92404 KB Output is correct
14 Correct 148 ms 96176 KB Output is correct
15 Correct 276 ms 92404 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 91948 KB Output is correct
2 Correct 36 ms 92144 KB Output is correct
3 Correct 268 ms 91756 KB Output is correct
4 Correct 520 ms 96176 KB Output is correct
5 Correct 572 ms 100784 KB Output is correct
6 Correct 652 ms 100784 KB Output is correct
7 Correct 408 ms 92720 KB Output is correct
8 Correct 504 ms 96176 KB Output is correct
9 Correct 156 ms 96176 KB Output is correct
10 Correct 280 ms 92400 KB Output is correct
11 Correct 268 ms 91996 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 92732 KB Output is correct
2 Correct 1160 ms 115432 KB Output is correct
3 Correct 420 ms 92720 KB Output is correct
4 Correct 1328 ms 128460 KB Output is correct
5 Correct 1516 ms 128716 KB Output is correct
6 Correct 704 ms 100784 KB Output is correct
7 Correct 408 ms 92720 KB Output is correct
8 Correct 120 ms 92720 KB Output is correct
9 Correct 1356 ms 165296 KB Output is correct
10 Correct 1064 ms 122492 KB Output is correct
11 Correct 1280 ms 136084 KB Output is correct
12 Correct 1164 ms 126828 KB Output is correct