oj.uz

Submission #129684

# Submission time Handle Problem Language Result Execution time Memory
129684 2019-07-13T04:28:26 Z 윤교준(#3140) 물병 (JOI14_bottle) C++14
30 / 100
 2379 ms 406544 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 131 ms 117044 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 163 ms 130216 KB Output is correct
2 Correct 229 ms 136924 KB Output is correct
3 Correct 1090 ms 222504 KB Output is correct
4 Correct 1603 ms 289208 KB Output is correct
5 Correct 1788 ms 313248 KB Output is correct
6 Correct 1080 ms 221160 KB Output is correct
7 Correct 1534 ms 288700 KB Output is correct
8 Correct 1825 ms 313612 KB Output is correct
9 Correct 2379 ms 406544 KB Output is correct
10 Correct 1368 ms 289616 KB Output is correct
11 Correct 1449 ms 288824 KB Output is correct
12 Correct 735 ms 230456 KB Output is correct
13 Correct 900 ms 226684 KB Output is correct
14 Correct 657 ms 230644 KB Output is correct
15 Correct 959 ms 226612 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

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