제출 #1186120

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1186120		JooDdae	물병 (JOI14_bottle)	C++17	100 / 100	1851 ms	234512 KiB

bottle

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
const int INF = 1e9;

int n, m, k, q, chk[2020][2020], d[2020][2020], p[200200];
char s[2020][2020];
queue<array<int, 2>> qu;
vector<array<int, 3>> v, v2;

int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }

bool merge(int x, int y) {
	if((x = find(x)) == (y = find(y))) return 0;
	p[x] = y;
	return 1;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> k >> q;
	for(int i=1;i<=n;i++) cin >> s[i]+1;
	for(int i=1;i<=k;i++) {
		int x, y; cin >> x >> y;
		chk[x][y] = i, qu.push({x, y});
	}

	while(!qu.empty()) {
		auto [x, y] = qu.front(); qu.pop();
		int c = chk[x][y], p = d[x][y];

		for(int i=0;i<4;i++) {
			int xx = x+dx[i], yy = y+dy[i];
			if(xx < 1 || yy < 1 || xx > n || yy > m || s[xx][yy] == '#') continue;
			if(chk[xx][yy]) {
				v.push_back({p+d[xx][yy], c, chk[xx][yy]});
			} else {
				chk[xx][yy] = c, d[xx][yy] = p+1, qu.push({xx, yy});
			}
		}
	}


	sort(v.begin(), v.end()), iota(p+1, p+1+k, 1);
	for(auto V : v) if(merge(V[1], V[2])) v2.push_back(V);
	swap(v, v2);

	vector<array<int, 5>> t(q);
	for(auto &[l, r, s, e, id] : t) cin >> s >> e, l = 0, r = 1e9;
	for(int i=0;i<q;i++) t[i][4] = i;

	int flag = 1;
	while(flag--) {
		iota(p+1, p+1+k, 1);
		sort(t.begin(), t.end());

		int i = 0;
		for(auto &[l, r, s, e, id] : t) if(l <= r) {
			flag = 1;

			int m = (l+r) >> 1;
			while(i < v.size() && v[i][0] <= m) merge(v[i][1], v[i][2]), i++;

			if(find(s) == find(e)) r = m-1;
			else l = m+1;
		}
	}

	vector<int> ans(q);
	for(auto [l, r, s, e, id] : t) ans[id] = (l >= INF ? -1 : l);
	for(int i=0;i<q;i++) cout << ans[i] << "\n";
}

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