oj.uz

Submission #5773

# Submission time Handle Problem Language Result Execution time Memory
5773 2014-05-17T07:13:24 Z ainta 물병 (JOI14_bottle) C++
60 / 100
 1244 ms 182176 KB 
#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
#define X first
#define Y second
#define W_ 2010
#define N_ 200010
#define INF 999999999
#define PII pair<int, int>
using namespace std;
int H, W, n, Query, D[W_][W_], P[W_][W_], cnt, par[N_];
int pp[18][N_], LL[18][N_], Dep[N_];
vector<int>E[N_], L[N_];
priority_queue<PII>PQ;
struct Edge{
	int a, b, d;
	bool operator <(const Edge &p)const{
		return d<p.d;
	}
}Ed[W_*W_*2];
char p[W_][W_];
void Do(int x, int y, int d, int pv){
	if (D[x][y] == -1){
		D[x][y] = 0;
		Ed[cnt].a = pv, Ed[cnt].b = P[x][y], Ed[cnt].d = d - 1;
		cnt++;
		PQ.push(PII(0, x*(W + 1) + y));
	}
	if (p[x][y] == '.' && D[x][y] > d){
		P[x][y] = pv, D[x][y] = d;
		PQ.push(PII(-d, x*(W + 1) + y));
	}
}
void BFS(int x, int y, int d)
{
	if (d != D[x][y])return;
	d++;
	Do(x - 1, y, d, P[x][y]);
	Do(x + 1, y, d, P[x][y]);
	Do(x, y - 1, d, P[x][y]);
	Do(x, y + 1, d, 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;
	PII t;
	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);
		D[x][y] = -1, P[x][y] = i;
		par[i] = i;
	}
	for (i = 1; i <= H; i++){
		for (j = 1; j <= W; j++){
			if (D[i][j] == -1){
				D[i][j] = 0;
				PQ.push(PII(0, i*(W + 1) + j));
				while (!PQ.empty()){
					t = PQ.top();
					PQ.pop();
					BFS(t.Y / (W + 1), t.Y % (W + 1), -t.X);
				}
			}
		}
	}
	sort(Ed, Ed + cnt);
	for (i = 0; i < cnt; 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
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 170476 KB Output is correct
2 Correct 4 ms 170476 KB Output is correct
3 Correct 8 ms 170476 KB Output is correct
4 Correct 104 ms 170476 KB Output is correct
5 Correct 96 ms 170476 KB Output is correct
6 Incorrect 88 ms 170476 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 170476 KB Output is correct
2 Correct 80 ms 170740 KB Output is correct
3 Correct 544 ms 170740 KB Output is correct
4 Correct 804 ms 170872 KB Output is correct
5 Correct 936 ms 171000 KB Output is correct
6 Correct 556 ms 170740 KB Output is correct
7 Correct 788 ms 170872 KB Output is correct
8 Correct 936 ms 171000 KB Output is correct
9 Correct 1052 ms 171000 KB Output is correct
10 Correct 800 ms 170476 KB Output is correct
11 Correct 768 ms 170608 KB Output is correct
12 Correct 268 ms 170740 KB Output is correct
13 Correct 268 ms 170920 KB Output is correct
14 Correct 272 ms 170740 KB Output is correct
15 Correct 272 ms 170928 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 170476 KB Output is correct
2 Correct 84 ms 170476 KB Output is correct
3 Correct 520 ms 170476 KB Output is correct
4 Correct 812 ms 170872 KB Output is correct
5 Correct 928 ms 171000 KB Output is correct
6 Correct 1052 ms 171000 KB Output is correct
7 Correct 792 ms 170476 KB Output is correct
8 Correct 788 ms 170872 KB Output is correct
9 Correct 260 ms 170740 KB Output is correct
10 Correct 264 ms 170924 KB Output is correct
11 Correct 192 ms 170848 KB Output is correct

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 684 ms 171004 KB Output is correct
2 Incorrect 1244 ms 182176 KB Output isn't correct
3 Halted 0 ms 0 KB -