oj.uz

Submission #129726

# Submission time Handle Problem Language Result Execution time Memory
129726 2019-07-13T05:50:46 Z 윤교준(#3140) 물병 (JOI14_bottle) C++14
100 / 100
 4469 ms 417404 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

const int MAXN = 200055;
const int MAXH = 2005;
const int MAXW = 2005;

struct DJF {
	DJF() { init(); }
	int ud[MAXN];

	void init() { iota(ud, ud+MAXN, 0); }
	int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
	void uf(int a, int b) { ud[uf(b)] = uf(a); }
} djf;

vector<pair<int, pii>> EV;
vector<pii> G[MAXN];
int prt[18][MAXN], pmx[18][MAXN], dep[MAXN];

int D[MAXH][MAXW];
vector<int> T[MAXH][MAXW];

char A[MAXH][MAXW];
int B[MAXN], C[MAXN];

int H, W, N, Q;

int lca(int a, int b) {
	int ret = 0;
	if(dep[a] > dep[b]) swap(a, b);
	const int dt = dep[b] - dep[a];
	for(int i = 18; i--;) if(dt & (1<<i)) {
		upmax(ret, pmx[i][b]);
		b = prt[i][b];
	}
	if(a == b) return ret;
	for(int i = 18; i--;) if(prt[i][a] != prt[i][b]) {
		upmax(ret, pmx[i][a]);
		upmax(ret, pmx[i][b]);
		a = prt[i][a];
		b = prt[i][b];
	}
	upmax(ret, pmx[0][a]);
	upmax(ret, pmx[0][b]);
	a = prt[0][a];
	return a ? ret : -1;
}

void dfs(int i) {
	for(auto &e : G[i]) {
		int v, c; tie(v, c) = e;
		if(dep[v]) continue;
		dep[v] = dep[i] + 1;
		prt[0][v] = i;
		pmx[0][v] = c;
		dfs(v);
	}
}

void makeMST() {
	sorv(EV);
	for(auto &e : EV) {
		int a, b, c;
		c = e.first; tie(a, b) = e.second;
		if(djf.uf(a) == djf.uf(b)) continue;
		djf.uf(a, b);
		G[a].eb(b, c);
		G[b].eb(a, c);
	}
	for(int i = 1; i <= N; i++) if(!dep[i]) {
		dep[i] = 1;
		dfs(i);
	}
	for(int j = 1; j < 18; j++) for(int i = 1; i <= N; i++) {
		prt[j][i] = prt[j-1][prt[j-1][i]];
		pmx[j][i] = max(pmx[j-1][i], pmx[j-1][prt[j-1][i]]);
	}
}

void addEdge(int y, int x, int ny, int nx) {
	int c = D[y][x] + D[ny][nx];
	if(INF <= c) return;
	for(int a : T[y][x]) for(int b : T[ny][nx])
		EV.eb(c, pii(a, b));
}

void doBFS() {
	queue<pii> PQ;
	fill(D[0], D[MAXH-1]+MAXW, INF);
	for(int i = 1; i <= N; i++) {
		D[B[i]][C[i]] = 0;
		PQ.emplace(B[i], C[i]);
		T[B[i]][C[i]].eb(i);
	}
	for(int y, x, dst; !PQ.empty();) {
		tie(y, x) = PQ.front(); PQ.pop();
		dst = D[y][x] + 1;
		for(int dr = 0, ny, nx; dr < 4; dr++) {
			ny = y+dy[dr]; nx = x+dx[dr];
			if(ny < 1 || nx < 1 || H < ny || W < nx || '.' != A[ny][nx]) continue;
			addEdge(y, x, ny, nx);
			if(dst < D[ny][nx]) {
				D[ny][nx] = dst;
				T[ny][nx] = T[y][x];
				PQ.emplace(ny, nx);
				continue;
			}
			if(D[ny][nx] < dst) continue;
			for(int idx : T[y][x]) {
				if(3 < sz(T[ny][nx])) break;
				bool flag = false;
				for(int v : T[ny][nx]) {
					if(idx == v) {
						flag = true;
						break;
					}
				}
				if(!flag) {
					T[ny][nx].eb(idx);
				}
			}
		}
	}
}

int main() {
	scanf("%d%d%d%d", &H, &W, &N, &Q);
	for(int i = 1; i <= H; i++) scanf(" %s", A[i]+1);
	for(int i = 1; i <= N; i++) scanf("%d%d", &B[i], &C[i]);

	doBFS();
	makeMST();

	for(int a, b; Q--;) {
		scanf("%d%d", &a, &b);
		printf("%d\n", lca(a, b));
	}
	return 0;
}

Compilation message

bottle.cpp: In function 'int main()':
bottle.cpp:136:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &H, &W, &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:137:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= H; i++) scanf(" %s", A[i]+1);
                              ~~~~~^~~~~~~~~~~~~~~
bottle.cpp:138:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= N; i++) scanf("%d%d", &B[i], &C[i]);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:144:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 117016 KB Output is correct
2 Correct 116 ms 117548 KB Output is correct
3 Correct 124 ms 118180 KB Output is correct
4 Correct 203 ms 120152 KB Output is correct
5 Correct 202 ms 120196 KB Output is correct
6 Correct 200 ms 119616 KB Output is correct
7 Correct 201 ms 119808 KB Output is correct
8 Correct 209 ms 120736 KB Output is correct
9 Correct 193 ms 120000 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 130192 KB Output is correct
2 Correct 302 ms 136932 KB Output is correct
3 Correct 1360 ms 224612 KB Output is correct
4 Correct 2048 ms 291904 KB Output is correct
5 Correct 2529 ms 316480 KB Output is correct
6 Correct 1364 ms 224580 KB Output is correct
7 Correct 2094 ms 292040 KB Output is correct
8 Correct 2537 ms 317076 KB Output is correct
9 Correct 3478 ms 410292 KB Output is correct
10 Correct 1803 ms 292996 KB Output is correct
11 Correct 1882 ms 292356 KB Output is correct
12 Correct 968 ms 234108 KB Output is correct
13 Correct 1119 ms 230224 KB Output is correct
14 Correct 860 ms 234168 KB Output is correct
15 Correct 1080 ms 230268 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 130292 KB Output is correct
2 Correct 259 ms 137284 KB Output is correct
3 Correct 1031 ms 215888 KB Output is correct
4 Correct 2068 ms 292204 KB Output is correct
5 Correct 2716 ms 317260 KB Output is correct
6 Correct 3444 ms 411388 KB Output is correct
7 Correct 1901 ms 293364 KB Output is correct
8 Correct 2009 ms 291480 KB Output is correct
9 Correct 1034 ms 239312 KB Output is correct
10 Correct 1161 ms 230740 KB Output is correct
11 Correct 998 ms 212204 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1553 ms 230312 KB Output is correct
2 Correct 2644 ms 291328 KB Output is correct
3 Correct 1798 ms 293684 KB Output is correct
4 Correct 3544 ms 341848 KB Output is correct
5 Correct 4469 ms 417404 KB Output is correct
6 Correct 2367 ms 288308 KB Output is correct
7 Correct 1703 ms 290608 KB Output is correct
8 Correct 703 ms 227512 KB Output is correct
9 Correct 4330 ms 404896 KB Output is correct
10 Correct 1906 ms 260796 KB Output is correct
11 Correct 4080 ms 404180 KB Output is correct
12 Correct 3012 ms 329896 KB Output is correct