Submission #129690

# Submission time Handle Problem Language Result Execution time Memory
129690 2019-07-13T04:49:52 Z 이온조(#3139) 물병 (JOI14_bottle) C++14
0 / 100
788 ms 47652 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);
             ~~~~~^~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 6008 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 30840 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 30844 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 788 ms 47652 KB Output isn't correct
2 Halted 0 ms 0 KB -