oj.uz

답안 #129695

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
129695 2019-07-13T04:54:13 Z 임유진(#3141) 물병 (JOI14_bottle) C++14
0 / 100
 460 ms 46968 KB 
#include <stdio.h>
#include <queue>
#include <algorithm>

using namespace std;

#define MAXH 2005
#define MAXP 200005
#define fi first
#define se second

typedef pair<int, int> pii;

struct edge {
	int A, B, D;
} ed[8000005];

const int mm[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
char m[MAXH][MAXH];
pii bui[MAXP], que[MAXP];
queue<pii> q;
int dis[MAXH][MAXH], fro[MAXH][MAXH];
int en;
int uni[MAXP];
vector<pii> mst[MAXP];
pii par[20][MAXP];
int dep[MAXP];
bool chk[MAXP];

int guni(int x) { return x == uni[x] ? x : uni[x] = guni(uni[x]); }

void unite(int x, int y) { uni[guni(x)] = guni(y); }

void dfs(int x) {
	//printf("dfs(%d)\n", x);
	chk[x] = true;
	for(auto a : mst[x]) if(!chk[a.se]) {
		par[0][a.se] = make_pair(a.fi, x);
		dep[a.se] = dep[x] + 1;
		dfs(a.se);
	}
}

int lcad(int x, int y) {
	int ans = 0;
	if(dep[x] < dep[y]) swap(x, y);
	for(int i = 0; i < 20; i++) if((dep[x] - dep[y]) & (1 << i)) {
		ans = max(ans, par[i][x].fi);
		x = par[i][x].se;
	}
	if(x == y) return ans;
	for(int i = 19; i >= 0; i--) if(par[i][x].se != par[i][y].fi) {
		ans = max(ans, max(par[i][x].fi, par[i][y].fi));
		x = par[i][x].se;
		y = par[i][y].se;
	}
	return max(ans, max(par[0][x].fi, par[0][y].fi));
	return ans + par[0][x].fi + par[0][y].fi;
}

int main() {
	int H, W, P, Q;

	//freopen("input.txt", "r", stdin);

	scanf("%d%d%d%d", &H, &W, &P, &Q);
	for(int i = 1; i <= H; i++) scanf("%s", m[i] + 1);
	for(int i = 1; i <= P; i++) scanf("%d%d", &bui[i].fi, &bui[i].se);
	for(int i = 0; i < Q; i++) scanf("%d%d", &que[i].fi, &que[i].se);

	for(int i = 1; i <= H; i++) m[i][0] = m[i][W + 1] = '#';
	for(int i = 1; i <= W; i++) m[0][i] = m[H + 1][i] = '#';

	for(int i = 1; i <= P; i++) {
		fro[bui[i].fi][bui[i].se] = i;
		q.push(bui[i]);
	}
	while(!q.empty()) {
		pii t = q.front();
		q.pop();
		for(int i = 0; i < 4; i++) {
			int a = t.fi + mm[i][0], b = t.se + mm[i][1];
			if(fro[a][b] == 0 && m[a][b] == '.') {
				fro[a][b] = fro[t.fi][t.se];
				dis[a][b] = dis[t.fi][t.se] + 1;
				q.push(make_pair(a, b));
			}
		}
	}
/*
	for(int i = 1; i <= H; i++) {
		for(int j = 1; j <= W; j++) printf("(%d, %d)", dis[i][j], fro[i][j]);
		printf("\n");
	}
	*/

	for(int i = 1; i <= H; i++) for(int j = 1; j < W; j++) 
		if(m[i][j] == '.' && m[i][j + 1] == '.' && fro[i][j] != 0 && fro[i][j + 1] != 0 && fro[i][j] != fro[i][j + 1])
			ed[en++] = (edge) { fro[i][j], fro[i][j + 1], dis[i][j] + dis[i][j + 1] };
	for(int i = 1; i < H; i++) for(int j = 1; j <= W; j++) 
		if(m[i][j] == '.' && m[i + 1][j] == '.' && fro[i][j] != 0 && fro[i + 1][j] != 0 && fro[i][j] != fro[i + 1][j])
			ed[en++] = (edge) { fro[i][j], fro[i + 1][j], dis[i][j] + dis[i + 1][j] };

	//for(int i = 0; i < en; i++) printf("[%d %d %d]\n", ed[i].A, ed[i].B, ed[i].D);

	sort(ed, ed + en, [&](edge a, edge b) { return a.D < b.D; } );
	for(int i = 1; i <= P; i++) uni[i] = i;
	for(int i = 0; i < en; i++) if(guni(ed[i].A) != guni(ed[i].B)) {
		unite(ed[i].A, ed[i].B);
		mst[ed[i].A].push_back(make_pair(ed[i].D, ed[i].B));
		mst[ed[i].B].push_back(make_pair(ed[i].D, ed[i].A));
	}

	/*
	for(int i = 1; i <= P; i++) {
		for(auto a : mst[i]) printf("(%d, %d)", a.fi, a.se);
		printf("\n");
	}
	*/

	for(int i = 1; i <= P; i++) if(!chk[i]) {
		par[0][i].se = i;
		dfs(i);
	}
	/*
	for(int i = 1; i <= P; i++) printf("(%d, %d)", par[0][i].fi, par[0][i].se);
	printf("\n");
	*/
	for(int i = 1; i < 20; i++) for(int j = 1; j <= P; j++)
		par[i][j] = make_pair(max(par[i - 1][j].fi, par[i - 1][par[i - 1][j].se].fi), par[i - 1][par[i - 1][j].se].se);
	//printf("*\n");

	for(int i = 0; i < Q; i++) printf("%d\n", guni(que[i].fi) == guni(que[i].se) ? lcad(que[i].fi, que[i].se) : -1);
	return 0;
}

Compilation message

bottle.cpp: In function 'int main()':
bottle.cpp:66: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, &P, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:67: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", m[i] + 1);
                              ~~~~~^~~~~~~~~~~~~~~~
bottle.cpp:68:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= P; i++) scanf("%d%d", &bui[i].fi, &bui[i].se);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:69:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < Q; i++) scanf("%d%d", &que[i].fi, &que[i].se);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 6008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 27128 KB Output is correct
2 Correct 39 ms 10360 KB Output is correct
3 Correct 321 ms 41896 KB Output is correct
4 Correct 417 ms 43316 KB Output is correct
5 Correct 447 ms 44608 KB Output is correct
6 Correct 318 ms 41948 KB Output is correct
7 Correct 421 ms 43388 KB Output is correct
8 Correct 438 ms 44740 KB Output is correct
9 Correct 428 ms 46968 KB Output is correct
10 Correct 316 ms 41336 KB Output is correct
11 Incorrect 409 ms 42232 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 27000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 460 ms 45404 KB Output isn't correct
2 Halted 0 ms 0 KB -