oj.uz

Submission #129700

# Submission time Handle Problem Language Result Execution time Memory
129700 2019-07-13T05:01:34 Z 임유진(#3141) 물병 (JOI14_bottle) C++14
100 / 100
 1258 ms 98912 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].se) {
		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));
}

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(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(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:65: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:66: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:67: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:68: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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6008 KB Output is correct
2 Correct 12 ms 7416 KB Output is correct
3 Correct 12 ms 7672 KB Output is correct
4 Correct 101 ms 9932 KB Output is correct
5 Correct 98 ms 9984 KB Output is correct
6 Correct 96 ms 9888 KB Output is correct
7 Correct 94 ms 9916 KB Output is correct
8 Correct 97 ms 10104 KB Output is correct
9 Correct 93 ms 10088 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 27000 KB Output is correct
2 Correct 43 ms 10304 KB Output is correct
3 Correct 296 ms 41848 KB Output is correct
4 Correct 391 ms 43408 KB Output is correct
5 Correct 432 ms 44564 KB Output is correct
6 Correct 296 ms 41992 KB Output is correct
7 Correct 437 ms 43528 KB Output is correct
8 Correct 527 ms 44720 KB Output is correct
9 Correct 456 ms 46912 KB Output is correct
10 Correct 351 ms 41352 KB Output is correct
11 Correct 374 ms 42228 KB Output is correct
12 Correct 123 ms 36216 KB Output is correct
13 Correct 182 ms 35320 KB Output is correct
14 Correct 111 ms 36204 KB Output is correct
15 Correct 185 ms 35208 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 27000 KB Output is correct
2 Correct 33 ms 9264 KB Output is correct
3 Correct 286 ms 41080 KB Output is correct
4 Correct 425 ms 43512 KB Output is correct
5 Correct 461 ms 44864 KB Output is correct
6 Correct 479 ms 47224 KB Output is correct
7 Correct 418 ms 41592 KB Output is correct
8 Correct 402 ms 43640 KB Output is correct
9 Correct 135 ms 36600 KB Output is correct
10 Correct 189 ms 35448 KB Output is correct
11 Correct 192 ms 34512 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 45292 KB Output is correct
2 Correct 1081 ms 89192 KB Output is correct
3 Correct 320 ms 41464 KB Output is correct
4 Correct 1149 ms 93064 KB Output is correct
5 Correct 1258 ms 98272 KB Output is correct
6 Correct 635 ms 50040 KB Output is correct
7 Correct 320 ms 41432 KB Output is correct
8 Correct 96 ms 34296 KB Output is correct
9 Correct 1049 ms 98912 KB Output is correct
10 Correct 872 ms 88040 KB Output is correct
11 Correct 1181 ms 98716 KB Output is correct
12 Correct 928 ms 93960 KB Output is correct