oj.uz

Submission #129716

# Submission time Handle Problem Language Result Execution time Memory
129716 2019-07-13T05:35:55 Z 윤교준(#3140) 물병 (JOI14_bottle) C++14
10 / 100
 5000 ms 126588 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 univ(V) (V).erase(unique(allv(V)),(V).end())
#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() {
	for(int i = 1; i <= N; i++) {
		queue<pii> PQ;
		fill(D[0], D[H+2]+W+2, INF);
		D[B[i]][C[i]] = 0;
		PQ.emplace(B[i], C[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;
				if(D[ny][nx] <= dst) continue;
				D[ny][nx] = dst;
				PQ.emplace(ny, nx);
			}
		}
		for(int j = 1; j <= N; j++) if(i != j && D[B[j]][C[j]] < INF)
			EV.eb(D[B[j]][C[j]]-1, pii(i, j));
	}
}

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:120: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:121: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:122: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:128: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 194 ms 101696 KB Output is correct
2 Correct 245 ms 103172 KB Output is correct
3 Correct 408 ms 103272 KB Output is correct
4 Correct 485 ms 104816 KB Output is correct
5 Correct 495 ms 104948 KB Output is correct
6 Correct 397 ms 104724 KB Output is correct
7 Correct 396 ms 104660 KB Output is correct
8 Correct 371 ms 105004 KB Output is correct
9 Correct 332 ms 105068 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5063 ms 126504 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5043 ms 126588 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5016 ms 126312 KB Time limit exceeded
2 Halted 0 ms 0 KB -