oj.uz

Submission #5803

# Submission time Handle Problem Language Result Execution time Memory
5803 2014-05-17T10:39:23 Z ainta 물병 (JOI14_bottle) C++
100 / 100
 1472 ms 165296 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_], G[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;
	}
}tp;
vector<Edge>Ed;
char p[W_][W_];
void Do(int x, int y, int d, int pv){
	if (D[x][y] <= 0 && G[P[x][y]] > d-1){
		tp.a = pv, tp.b = P[x][y], tp.d = d - 1;
		Ed.push_back(tp);
		G[P[x][y]] = d - 1;
		if(D[x][y] == -1)PQ.push(PII(0, x*(W + 1) + y));
		D[x][y] = 0;
	}
	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()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	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;
		G[i] = INF;
	}
	for (i = 1; i <= H; i++){
		for (j = 1; j <= W; j++){
			if (D[i][j] == -1){
				D[i][j] = 0;
				G[P[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.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));
	}
}*/
#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] && 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 91564 KB Output is correct
2 Correct 8 ms 91756 KB Output is correct
3 Correct 4 ms 91564 KB Output is correct
4 Correct 88 ms 91564 KB Output is correct
5 Correct 88 ms 91756 KB Output is correct
6 Correct 88 ms 91564 KB Output is correct
7 Correct 92 ms 91564 KB Output is correct
8 Correct 92 ms 91948 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 24 ms 92144 KB Output is correct
2 Correct 40 ms 93872 KB Output is correct
3 Correct 372 ms 92720 KB Output is correct
4 Correct 504 ms 96176 KB Output is correct
5 Correct 528 ms 100784 KB Output is correct
6 Correct 356 ms 92720 KB Output is correct
7 Correct 496 ms 96176 KB Output is correct
8 Correct 536 ms 100784 KB Output is correct
9 Correct 572 ms 110000 KB Output is correct
10 Correct 352 ms 93872 KB Output is correct
11 Correct 432 ms 96176 KB Output is correct
12 Correct 144 ms 96176 KB Output is correct
13 Correct 264 ms 92780 KB Output is correct
14 Correct 136 ms 96176 KB Output is correct
15 Correct 240 ms 92784 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 92144 KB Output is correct
2 Correct 40 ms 92144 KB Output is correct
3 Correct 264 ms 91756 KB Output is correct
4 Correct 484 ms 96176 KB Output is correct
5 Correct 540 ms 100784 KB Output is correct
6 Correct 604 ms 110000 KB Output is correct
7 Correct 384 ms 93872 KB Output is correct
8 Correct 472 ms 96176 KB Output is correct
9 Correct 136 ms 96176 KB Output is correct
10 Correct 256 ms 92780 KB Output is correct
11 Correct 260 ms 92128 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 92732 KB Output is correct
2 Correct 1128 ms 115416 KB Output is correct
3 Correct 384 ms 93872 KB Output is correct
4 Correct 1368 ms 128500 KB Output is correct
5 Correct 1472 ms 165296 KB Output is correct
6 Correct 672 ms 100784 KB Output is correct
7 Correct 344 ms 93872 KB Output is correct
8 Correct 116 ms 92720 KB Output is correct
9 Correct 1316 ms 165296 KB Output is correct
10 Correct 1044 ms 122492 KB Output is correct
11 Correct 1312 ms 165296 KB Output is correct
12 Correct 1132 ms 139116 KB Output is correct