Submission #5803

#	Time	Username	Problem	Language	Result	Execution time	Memory
5803		ainta	물병 (JOI14_bottle)	C++98	100 / 100	1472 ms	165296 KiB

bottle

/*#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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30