oj.uz

Submission #129692

# Submission time Handle Problem Language Result Execution time Memory
129692 2019-07-13T04:50:53 Z 이온조(#3139) 물병 (JOI14_bottle) C++14
30 / 100
 1176 ms 47352 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;

const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0, 0};
const int _N = 200009;

vector<pii> adj[_N];
int A[_N], B[_N], D[2009][2009], um[2009][2009], U[_N], p[22][_N], mx[22][_N], l, in[_N], ou[_N], t;
bool vs[2009][2009];
char S[2009][2009];

int root(int x) {
	if(U[x] == x) return x;
	return U[x] = root(U[x]);
}

void merg(int u, int v, int w) {
	u = root(u); v = root(v);
	if(u != v) {
		// printf("%d <--> %d, cost: %d\n", u, v, w);
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		U[u] = v;
	}
}

bool isup(int u, int v) {
	return in[u] <= in[v] && ou[u] >= ou[v];
}

int get(int u, int v) {
	// printf("get: u: %d, v: %d\n", u, v);
	int ret = 0;
	if(isup(u, v)) swap(u, v);
	if(!isup(v, u)) {
		for(int i=l; i>=0; i--) {
			if(!isup(p[i][v], u)) {
				ret = max(ret, mx[i][v]);
				v = p[i][v];
			}
		}
		ret = max(ret, mx[0][v]);
		v = p[0][v];
	}
	assert(isup(v, u));
	for(int i=l; i>=0; i--) if(!isup(p[i][u], v) || p[i][u] == v) {
		ret = max(ret, mx[i][u]);
		u = p[i][u];
	}
	return ret;
}

void dfs(int x, int p, int w) {
	// printf("dfs: x: %d, p: %d, w: %d\n", x, p, w);
	in[x] = ++t; ::p[0][x] = p; mx[0][x] = w;
	for(auto& it: adj[x]) if(it.first != p) dfs(it.first, x, it.second);
	ou[x] = t;
}

int main() {
	int H, W, P, Q; scanf("%d%d%d%d",&H,&W,&P,&Q);
	for(int i=0; i<=H+1; i++) for(int j=0; j<=W+1; j++) S[i][j] = '#';
	for(int i=1; i<=H; i++) {
		for(int j=1; j<=W; j++) {
			scanf(" %c",&S[i][j]);
		}
	}
	queue<tiii> que;
	for(int i=1; i<=P; i++) {
		scanf("%d%d",&A[i],&B[i]);
		que.push((tiii){A[i], B[i], i});
		vs[A[i]][B[i]] = 1;
		um[A[i]][B[i]] = i;
		U[i] = i;
	}
	while(que.size()) {
		int x, y, id; tie(x, y, id) = que.front(); que.pop();
		for(int k=0; k<4; k++) {
			int X = x+dx[k], Y = y+dy[k];
			if(!vs[X][Y] && S[X][Y] != '#') {
				vs[X][Y] = 1;
				D[X][Y] = D[x][y] + 1;
				um[X][Y] = id;
				que.push((tiii){X, Y, id});
			}
			else {
				if(S[X][Y] == '#') continue;
				merg(id, um[X][Y], D[x][y] + D[X][Y]);
			}
		}
	}
	for(int i=1; i<=P; i++) if(p[0][i] == 0) dfs(i, i, 0);
	for(int i=1; (1<<i)<=P; i++) {
		for(int j=1; j<=P; j++) {
			p[i][j] = p[i-1][p[i-1][j]];
			mx[i][j] = max(mx[i-1][j], mx[i-1][p[i-1][j]]);
		}
		l = i;
	}
	// printf("l: %d\n", l);
	while(Q--) {
		int S, T; scanf("%d%d",&S,&T);
		if(root(S) != root(T)) puts("-1");
		else printf("%d\n", get(S, T));
	}
	return 0;
}

Compilation message

bottle.cpp: In function 'int main()':
bottle.cpp:64:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int H, W, P, Q; scanf("%d%d%d%d",&H,&W,&P,&Q);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:68:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c",&S[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~
bottle.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A[i],&B[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~
bottle.cpp:105:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int S, T; scanf("%d%d",&S,&T);
             ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 6008 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 66 ms 30812 KB Output is correct
2 Correct 80 ms 10360 KB Output is correct
3 Correct 662 ms 45684 KB Output is correct
4 Correct 933 ms 46328 KB Output is correct
5 Correct 1022 ms 46948 KB Output is correct
6 Correct 655 ms 45916 KB Output is correct
7 Correct 876 ms 46556 KB Output is correct
8 Correct 1004 ms 46996 KB Output is correct
9 Correct 1176 ms 47340 KB Output is correct
10 Correct 825 ms 45048 KB Output is correct
11 Correct 844 ms 45520 KB Output is correct
12 Correct 383 ms 39056 KB Output is correct
13 Correct 452 ms 38472 KB Output is correct
14 Correct 379 ms 39160 KB Output is correct
15 Correct 457 ms 38520 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

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