Submission #129837

#	Time	Username	Problem	Language	Result	Execution time	Memory
129837		onjo0127	물병 (JOI14_bottle)	C++11	100 / 100	2529 ms	138576 KiB

bottle

#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 sz = que.size();
		vector<tiii> W;
		while(sz--) {
			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(S[X][Y] == '#') continue;
				if(!vs[X][Y]) {
					vs[X][Y] = 1;
					D[X][Y] = D[x][y] + 1;
					um[X][Y] = id;
					que.push((tiii){X, Y, id});
				}
				else {
					W.push_back((tiii){D[x][y] + D[X][Y], id, um[X][Y]});
				}
			}
		}
		sort(W.begin(), W.end());
		for(auto& it: W) {
			int w, u, v; tie(w, u, v) = it;
			merg(u, v, w);
		}
	}
	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 (stderr)

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:114: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: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30