Submission #18528

#	Time	Username	Problem	Language	Result	Execution time	Memory
18528		choyi0521	물병 (JOI14_bottle)	C++14	60 / 100	745 ms	102200 KiB

bottle

#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_P = 200000, LGP=17;
const int fx[] = { 1,0,-1,0 }, fy[] = { 0,1,0,-1 };
int h, w,p,q, ck[2001][2001],dist[2001][2001];
char map[2001][2002];
vector<pair<int, int>> adj[MAX_P+1];
struct uf {
	int par[MAX_P+1],rnk[MAX_P+1];
	uf(){
		for (int i = 1; i <= MAX_P; i++)
			par[i] = i, rnk[i] = 0;
	}
	int find(int x) {
		if (x == par[x]) return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		if (rnk[x] > rnk[y]) par[y] = x;
		else {
			par[x] = y;
			if (rnk[x] == rnk[y]) rnk[y]++;
		}
	}
}st;
struct qst {
	int x, y,idx,dis;
};
struct edge {
	int x, y,d;
	bool operator<(edge i) const {
		return d < i. d;
	}
};
vector<edge> e;
bool dck[MAX_P + 1];
int dp[MAX_P + 1][LGP + 1],maxi[MAX_P+1][LGP+1],lv[MAX_P+1];
void dfs(int h) {
	dck[h] = true;
	for (auto t : adj[h]) {
		if (dck[t.first]) continue;
		lv[t.first] = lv[h] + 1;
		dp[t.first][0] = h;
		maxi[t.first][0] = t.second;
		for (int i = 1; i <= LGP; i++) {
			dp[t.first][i] = dp[dp[t.first][i - 1]][i - 1];
			maxi[t.first][i] = max(maxi[dp[t.first][i - 1]][i - 1], maxi[t.first][i - 1]);
		}
		dfs(t.first);
	}
}
int lca(int x, int y) {
	if (lv[x] < lv[y]) swap(x, y);
	int res = 0;
	for (int i = LGP; i >= 0; i--)
		if (lv[x] - lv[y] >= 1 << i) res = max(res, maxi[x][i]),x = dp[x][i];
	if (x == y) return res;
	for (int i = LGP; i >= 0; i--) {
		if (dp[x][i] != dp[y][i]) {
			res = max({ res,maxi[x][i],maxi[y][i] });
			x = dp[x][i];
			y = dp[y][i];
		}
	}
	return max({ res,maxi[x][0],maxi[y][0] });
}
int main() {
	scanf("%d %d %d %d", &h, &w, &p, &q);
	for (int i = 1; i <= h; i++) scanf("%s", map[i] + 1);
	queue<qst> que;
	for (int i = 1; i <= p; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		que.push({ x,y,i,0 });
	}
	while (!que.empty()) {
		qst he = que.front();
		que.pop();
		if (he.x<1 || he.y<1 || he.x>h || he.y>w || map[he.x][he.y]=='#') continue;
		if (ck[he.x][he.y]) {
			if (ck[he.x][he.y] != he.idx)
				e.push_back({ ck[he.x][he.y],he.idx,dist[he.x][he.y] + he.dis - 1 });
			continue;
		}
		ck[he.x][he.y] = he.idx;
		dist[he.x][he.y] = he.dis;
		for (int i = 0; i < 4; i++)
			que.push({ he.x + fx[i],he.y + fy[i],he.idx,he.dis + 1 });
	}
	sort(e.begin(), e.end());
	for (auto it : e) {
		int rx = st.find(it.x), ry = st.find(it.y);
		if (rx == ry) continue;
		adj[it.x].push_back({ it.y,it.d });
		adj[it.y].push_back({ it.x,it.d });
		st.unite(rx, ry);
	}
	dfs(1);
	for (int i = 0; i < q; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		if (st.find(x) != st.find(y)) puts("-1");
		else printf("%d\n", lca(x, y));
	}
	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 0 / 30