oj.uz

Submission #129683

# Submission time Handle Problem Language Result Execution time Memory
129683 2019-07-13T04:25:45 Z 윤교준(#3140) 물병 (JOI14_bottle) C++14
30 / 100
 2444 ms 410488 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() {
	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:135: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:136: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:137: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:143: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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 117172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 130336 KB Output is correct
2 Correct 233 ms 136872 KB Output is correct
3 Correct 1082 ms 225336 KB Output is correct
4 Correct 1669 ms 292460 KB Output is correct
5 Correct 1791 ms 316884 KB Output is correct
6 Correct 1194 ms 224628 KB Output is correct
7 Correct 1559 ms 292124 KB Output is correct
8 Correct 1785 ms 317200 KB Output is correct
9 Correct 2444 ms 410488 KB Output is correct
10 Correct 1379 ms 293184 KB Output is correct
11 Correct 1478 ms 292304 KB Output is correct
12 Correct 812 ms 234052 KB Output is correct
13 Correct 886 ms 230208 KB Output is correct
14 Correct 698 ms 234332 KB Output is correct
15 Correct 907 ms 230200 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 166 ms 130468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1253 ms 231200 KB Output isn't correct
2 Halted 0 ms 0 KB -