oj.uz

Submission #5774

# Submission time Handle Problem Language Result Execution time Memory
5774 2014-05-17T07:13:40 Z ainta 물병 (JOI14_bottle) C++
60 / 100
 1240 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 12 ms 170476 KB Output is correct
4 Correct 96 ms 170476 KB Output is correct
5 Correct 100 ms 170476 KB Output is correct
6 Incorrect 84 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 84 ms 170740 KB Output is correct
3 Correct 548 ms 170740 KB Output is correct
4 Correct 816 ms 170872 KB Output is correct
5 Correct 912 ms 171000 KB Output is correct
6 Correct 532 ms 170740 KB Output is correct
7 Correct 820 ms 170872 KB Output is correct
8 Correct 924 ms 171000 KB Output is correct
9 Correct 1036 ms 171000 KB Output is correct
10 Correct 776 ms 170476 KB Output is correct
11 Correct 764 ms 170608 KB Output is correct
12 Correct 276 ms 170740 KB Output is correct
13 Correct 272 ms 170924 KB Output is correct
14 Correct 288 ms 170740 KB Output is correct
15 Correct 268 ms 170924 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 170476 KB Output is correct
2 Correct 76 ms 170476 KB Output is correct
3 Correct 516 ms 170476 KB Output is correct
4 Correct 808 ms 170872 KB Output is correct
5 Correct 936 ms 171000 KB Output is correct
6 Correct 1048 ms 171000 KB Output is correct
7 Correct 780 ms 170476 KB Output is correct
8 Correct 788 ms 170872 KB Output is correct
9 Correct 276 ms 170740 KB Output is correct
10 Correct 276 ms 170920 KB Output is correct
11 Correct 196 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 1240 ms 182176 KB Output isn't correct
3 Halted 0 ms 0 KB -