oj.uz

Submission #129723

# Submission time Handle Problem Language Result Execution time Memory
129723 2019-07-13T05:49:46 Z 윤교준(#3140) 물병 (JOI14_bottle) C++14
100 / 100
 4651 ms 415992 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 114 ms 117020 KB Output is correct
2 Correct 115 ms 117496 KB Output is correct
3 Correct 120 ms 118072 KB Output is correct
4 Correct 224 ms 119360 KB Output is correct
5 Correct 218 ms 119324 KB Output is correct
6 Correct 197 ms 118636 KB Output is correct
7 Correct 197 ms 118944 KB Output is correct
8 Correct 206 ms 119768 KB Output is correct
9 Correct 191 ms 119012 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 130200 KB Output is correct
2 Correct 329 ms 136872 KB Output is correct
3 Correct 1354 ms 224076 KB Output is correct
4 Correct 2148 ms 290628 KB Output is correct
5 Correct 2530 ms 315080 KB Output is correct
6 Correct 1311 ms 223032 KB Output is correct
7 Correct 2150 ms 290636 KB Output is correct
8 Correct 2584 ms 315688 KB Output is correct
9 Correct 3578 ms 408464 KB Output is correct
10 Correct 1818 ms 291836 KB Output is correct
11 Correct 1900 ms 291012 KB Output is correct
12 Correct 961 ms 232760 KB Output is correct
13 Correct 1160 ms 228936 KB Output is correct
14 Correct 887 ms 232804 KB Output is correct
15 Correct 1127 ms 228920 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 130412 KB Output is correct
2 Correct 260 ms 137180 KB Output is correct
3 Correct 1027 ms 214124 KB Output is correct
4 Correct 2061 ms 290300 KB Output is correct
5 Correct 2555 ms 315608 KB Output is correct
6 Correct 3600 ms 409676 KB Output is correct
7 Correct 1783 ms 291988 KB Output is correct
8 Correct 2023 ms 290232 KB Output is correct
9 Correct 1016 ms 237876 KB Output is correct
10 Correct 1225 ms 229432 KB Output is correct
11 Correct 1045 ms 210796 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1532 ms 226868 KB Output is correct
2 Correct 2672 ms 288748 KB Output is correct
3 Correct 1822 ms 292848 KB Output is correct
4 Correct 3591 ms 340020 KB Output is correct
5 Correct 4651 ms 415992 KB Output is correct
6 Correct 2387 ms 289812 KB Output is correct
7 Correct 1841 ms 293196 KB Output is correct
8 Correct 724 ms 229964 KB Output is correct
9 Correct 4550 ms 407204 KB Output is correct
10 Correct 2028 ms 263992 KB Output is correct
11 Correct 4163 ms 407736 KB Output is correct
12 Correct 3102 ms 334856 KB Output is correct