oj.uz

Submission #146586

# Submission time Handle Problem Language Result Execution time Memory
146586 2019-08-24T14:58:01 Z maruii 물병 (JOI14_bottle) C++14
100 / 100
 1914 ms 238916 KB 
#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;
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1344 KB Output is correct
2 Correct 8 ms 2240 KB Output is correct
3 Correct 11 ms 2812 KB Output is correct
4 Correct 84 ms 4720 KB Output is correct
5 Correct 80 ms 4604 KB Output is correct
6 Correct 83 ms 4344 KB Output is correct
7 Correct 77 ms 4408 KB Output is correct
8 Correct 92 ms 5112 KB Output is correct
9 Correct 87 ms 4636 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 17280 KB Output is correct
2 Correct 86 ms 10880 KB Output is correct
3 Correct 613 ms 89536 KB Output is correct
4 Correct 1004 ms 139144 KB Output is correct
5 Correct 1373 ms 140120 KB Output is correct
6 Correct 611 ms 89444 KB Output is correct
7 Correct 1016 ms 139352 KB Output is correct
8 Correct 1271 ms 139820 KB Output is correct
9 Correct 1834 ms 238916 KB Output is correct
10 Correct 837 ms 138644 KB Output is correct
11 Correct 937 ms 138840 KB Output is correct
12 Correct 377 ms 73820 KB Output is correct
13 Correct 468 ms 76976 KB Output is correct
14 Correct 368 ms 73956 KB Output is correct
15 Correct 471 ms 76108 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 17452 KB Output is correct
2 Correct 79 ms 10648 KB Output is correct
3 Correct 504 ms 89144 KB Output is correct
4 Correct 1031 ms 139288 KB Output is correct
5 Correct 1320 ms 139940 KB Output is correct
6 Correct 1914 ms 238884 KB Output is correct
7 Correct 816 ms 138636 KB Output is correct
8 Correct 993 ms 139424 KB Output is correct
9 Correct 379 ms 73948 KB Output is correct
10 Correct 468 ms 76464 KB Output is correct
11 Correct 444 ms 52236 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 89868 KB Output is correct
2 Correct 1108 ms 98028 KB Output is correct
3 Correct 973 ms 138480 KB Output is correct
4 Correct 1520 ms 148852 KB Output is correct
5 Correct 1900 ms 150604 KB Output is correct
6 Correct 1203 ms 140772 KB Output is correct
7 Correct 872 ms 138504 KB Output is correct
8 Correct 333 ms 73424 KB Output is correct
9 Correct 1768 ms 134600 KB Output is correct
10 Correct 810 ms 85104 KB Output is correct
11 Correct 1690 ms 143952 KB Output is correct
12 Correct 1307 ms 139380 KB Output is correct