oj.uz

Submission #282113

# Submission time Handle Problem Language Result Execution time Memory
282113 2020-08-24T03:10:34 Z jjwdi0 물병 (JOI14_bottle) C++11
100 / 100
 1615 ms 125648 KB 
#include <bits/stdc++.h>
using namespace std;
using pr = pair<int, int>;
using qr = pair<pr, pr>;
using tr = pair<int, pr>;

int N, M, K, Q, X[200005], Y[200005], d[4] = { 0,0,1,-1 }, par[200005], st1[200005][20], st2[200005][20], lev[200005];
pr D[2005][2005];
char A[2005][2005];
vector<tr> edge;
vector<pr> v[200005];
queue<qr> q;

int f(int x) { return par[x] = (par[x] == x ? x : f(par[x])); }
void uni(int x, int y) { par[f(y)] = par[f(x)]; }

void dfs(int x, int p) {
	lev[x] = lev[p] + 1, st1[x][0] = p;
	for(auto it : v[x]) {
		if(it.first == p) st2[x][0] = it.second;
		else dfs(it.first, x);
	}
}

int query(int x, int y) {
	if(f(x) != f(y)) return -1;
	int res = 0;
	if(lev[x] > lev[y]) swap(x, y);
	for(int i=0; i<20; i++) if((lev[y] - lev[x]) & (1 << i)) res = max(res, st2[y][i]), y = st1[y][i];
	if(x == y) return res;
	for(int i=19; ~i; i--) if(st1[x][i] != st1[y][i]) res = max({ res, st2[x][i], st2[y][i] }), x = st1[x][i], y = st1[y][i];
	assert(st1[x][0] == st1[y][0]);
	return max({ res, st2[x][0], st2[y][0] });
}

int main() {
	scanf("%d %d %d %d", &N, &M, &K, &Q);
	for(int i=1; i<=N; i++) scanf("%s", A[i] + 1);
	for(int i=1; i<=K; i++) scanf("%d %d", X+i, Y+i), q.push(qr(pr(0, i), pr(X[i], Y[i]))), D[X[i]][Y[i]] = pr(0, i);
	while(!q.empty()) {
		int u = q.front().first.second, dist = q.front().first.first, x = q.front().second.first, y = q.front().second.second; q.pop();
		for(int i=0; i<4; i++) {
			int xx = x + d[i], yy = y + d[3-i];
			if(xx < 1 || yy < 1 || xx > N || yy > M || D[xx][yy].second == u || A[xx][yy] == '#') continue;
			if(D[xx][yy].second) edge.push_back(tr(D[xx][yy].first + dist, pr(u, D[xx][yy].second)));
			else D[xx][yy] = pr(dist + 1, u), q.push(qr(D[xx][yy], pr(xx, yy)));
		}
	}
	iota(par, par + K + 1, 0);
	sort(edge.begin(), edge.end());
	for(auto it : edge) {
		int cost = it.first, x = it.second.first, y = it.second.second;
		if(f(x) == f(y)) continue;
		uni(x, y);
		v[x].push_back(pr(y, cost));
		v[y].push_back(pr(x, cost));
	}
	for(int i=1; i<=K; i++) if(!lev[i]) dfs(i, 0);
	for(int i=1; i<20; i++) for(int j=1; j<=K; j++) {
		st1[j][i] = st1[st1[j][i-1]][i-1];
		st2[j][i] = max(st2[j][i-1], st2[st1[j][i-1]][i-1]);
	}
	while(Q--) {
		int x, y;
		scanf("%d %d", &x, &y);
		printf("%d\n", query(x, y));
	}
}

Compilation message

bottle.cpp: In function 'int main()':
bottle.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |  scanf("%d %d %d %d", &N, &M, &K, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:38:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |  for(int i=1; i<=N; i++) scanf("%s", A[i] + 1);
      |                          ~~~~~^~~~~~~~~~~~~~~~
bottle.cpp:39:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  for(int i=1; i<=K; i++) scanf("%d %d", X+i, Y+i), q.push(qr(pr(0, i), pr(X[i], Y[i]))), D[X[i]][Y[i]] = pr(0, i);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~
bottle.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |   scanf("%d %d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5632 KB Output is correct
2 Correct 7 ms 6656 KB Output is correct
3 Correct 8 ms 6784 KB Output is correct
4 Correct 103 ms 8792 KB Output is correct
5 Correct 105 ms 8824 KB Output is correct
6 Correct 105 ms 8568 KB Output is correct
7 Correct 100 ms 8728 KB Output is correct
8 Correct 111 ms 9148 KB Output is correct
9 Correct 98 ms 8952 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 19212 KB Output is correct
2 Correct 44 ms 10796 KB Output is correct
3 Correct 361 ms 42416 KB Output is correct
4 Correct 503 ms 45216 KB Output is correct
5 Correct 571 ms 52636 KB Output is correct
6 Correct 351 ms 46388 KB Output is correct
7 Correct 488 ms 49376 KB Output is correct
8 Correct 554 ms 52644 KB Output is correct
9 Correct 633 ms 59688 KB Output is correct
10 Correct 413 ms 46512 KB Output is correct
11 Correct 459 ms 48424 KB Output is correct
12 Correct 162 ms 38176 KB Output is correct
13 Correct 229 ms 35712 KB Output is correct
14 Correct 148 ms 38180 KB Output is correct
15 Correct 240 ms 35936 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 19192 KB Output is correct
2 Correct 31 ms 9384 KB Output is correct
3 Correct 251 ms 44792 KB Output is correct
4 Correct 505 ms 49376 KB Output is correct
5 Correct 577 ms 52768 KB Output is correct
6 Correct 639 ms 59852 KB Output is correct
7 Correct 421 ms 46708 KB Output is correct
8 Correct 484 ms 49636 KB Output is correct
9 Correct 169 ms 38308 KB Output is correct
10 Correct 262 ms 35856 KB Output is correct
11 Correct 218 ms 34248 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 44460 KB Output is correct
2 Correct 1131 ms 100724 KB Output is correct
3 Correct 444 ms 46384 KB Output is correct
4 Correct 1388 ms 110592 KB Output is correct
5 Correct 1615 ms 123232 KB Output is correct
6 Correct 712 ms 58336 KB Output is correct
7 Correct 416 ms 46512 KB Output is correct
8 Correct 128 ms 35244 KB Output is correct
9 Correct 1503 ms 125648 KB Output is correct
10 Correct 1057 ms 92848 KB Output is correct
11 Correct 1462 ms 120244 KB Output is correct
12 Correct 1226 ms 106420 KB Output is correct