oj.uz

Submission #5785

# Submission time Handle Problem Language Result Execution time Memory
5785 2014-05-17T09:34:26 Z ainta 물병 (JOI14_bottle) C++
70 / 100
 1788 ms 97212 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;
		cnt++;
		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()
{
	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));
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 76568 KB Output is correct
2 Correct 76 ms 77124 KB Output is correct
3 Correct 544 ms 76904 KB Output is correct
4 Correct 840 ms 77180 KB Output is correct
5 Correct 952 ms 77288 KB Output is correct
6 Correct 548 ms 76904 KB Output is correct
7 Correct 848 ms 77164 KB Output is correct
8 Correct 956 ms 77288 KB Output is correct
9 Correct 1064 ms 77288 KB Output is correct
10 Correct 816 ms 76568 KB Output is correct
11 Correct 784 ms 76832 KB Output is correct
12 Correct 288 ms 77100 KB Output is correct
13 Correct 268 ms 77240 KB Output is correct
14 Correct 292 ms 77100 KB Output is correct
15 Correct 264 ms 77244 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 76568 KB Output is correct
2 Correct 80 ms 76568 KB Output is correct
3 Correct 524 ms 76568 KB Output is correct
4 Correct 836 ms 77164 KB Output is correct
5 Correct 944 ms 77288 KB Output is correct
6 Correct 1080 ms 77288 KB Output is correct
7 Correct 812 ms 76568 KB Output is correct
8 Correct 792 ms 77164 KB Output is correct
9 Correct 288 ms 77084 KB Output is correct
10 Correct 272 ms 77240 KB Output is correct
11 Correct 204 ms 77132 KB Output is correct

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 77192 KB Output is correct
2 Correct 1268 ms 94432 KB Output is correct
3 Correct 856 ms 76568 KB Output is correct
4 Correct 1652 ms 96072 KB Output is correct
5 Correct 1788 ms 97212 KB Output is correct
6 Correct 992 ms 78788 KB Output is correct
7 Correct 784 ms 76700 KB Output is correct
8 Correct 284 ms 76568 KB Output is correct
9 Incorrect 1420 ms 96196 KB Output isn't correct
10 Halted 0 ms 0 KB -