제출 #146586

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
146586		maruii	물병 (JOI14_bottle)	C++14	100 / 100	1914 ms	238916 KiB

bottle

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second

char S[2005][2005];
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
pii vis[2005][2005]; // sc, dist
queue<pair<pii, int> > q; // x, y, sc
int maxDist;

pii upa[200005];
int rnk[200005];
int fnd(int x, int c) { return upa[x].ss > c ? x : fnd(upa[x].ff, c); }
void uni(int x, int y, int c) {
	x = fnd(x, c), y = fnd(y, c);
	if (x == y) return;
	if (rnk[x] < rnk[y]) swap(x, y);
	upa[y] = pii(x, c);
	if (rnk[x] == rnk[y]) ++rnk[x];
	maxDist = max(maxDist, c);
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int H, W, P, Q; cin >> H >> W >> P >> Q;
	for (int i = 1; i <= H; ++i) cin >> S[i] + 1;
	for (int i = 1; i <= P; ++i) {
		int x, y; cin >> x >> y;
		vis[x][y].ff = i;
		q.emplace(pii(x, y), i);
		upa[i] = pii(i, 1e9);
	}
	
	vector<pair<int, pii> > E;
	while (q.size()) {
		auto cur = q.front(); q.pop();
		int x = cur.ff.ff, y = cur.ff.ss;
		int sc = cur.ss, dist = vis[x][y].ss;

		for (int i = 0; i < 4; ++i) {
			int nx = x + dx[i], ny = y + dy[i];
			if (nx < 1 || nx > H || ny < 1 || ny > W || S[nx][ny] == '#') continue;
			if (vis[nx][ny].ff) {
				E.emplace_back(dist + vis[nx][ny].ss, pii(sc, vis[nx][ny].ff));
				continue;
			}
			vis[nx][ny] = pii(sc, dist + 1);
			q.emplace(pii(nx, ny), sc);
		}
	}
	
	sort(E.begin(), E.end());
	
	for (auto i : E) {
		uni(i.ss.ff, i.ss.ss, i.ff);
	}
	
	for (int i = 0; i < Q; ++i) {
		int x, y; cin >> x >> y;
		if (fnd(x, maxDist) != fnd(y, maxDist)) {
			cout << -1 << '\n';
			continue;
		}
		int l = 0, r = maxDist;
		while (l < r) {
			int m = l + r >> 1;
			if (fnd(x, m) == fnd(y, m)) r = m;
			else l = m + 1;
		}
		cout << l << '\n';
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bottle.cpp: In function 'int main()':
bottle.cpp:28:43: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  for (int i = 1; i <= H; ++i) cin >> S[i] + 1;
                                      ~~~~~^~~
bottle.cpp:68:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m = l + r >> 1;
            ~~^~~

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