oj.uz

Submission #129698

# Submission time Handle Problem Language Result Execution time Memory
129698 2019-07-13T05:00:19 Z 이온조(#3139) 물병 (JOI14_bottle) C++14
100 / 100
 2532 ms 130664 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 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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6136 KB Output is correct
2 Correct 13 ms 7800 KB Output is correct
3 Correct 17 ms 8056 KB Output is correct
4 Correct 95 ms 8568 KB Output is correct
5 Correct 97 ms 8568 KB Output is correct
6 Correct 91 ms 8556 KB Output is correct
7 Correct 88 ms 8540 KB Output is correct
8 Correct 100 ms 8816 KB Output is correct
9 Correct 95 ms 8796 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 31012 KB Output is correct
2 Correct 114 ms 10900 KB Output is correct
3 Correct 894 ms 46620 KB Output is correct
4 Correct 1220 ms 50696 KB Output is correct
5 Correct 1651 ms 55848 KB Output is correct
6 Correct 935 ms 46624 KB Output is correct
7 Correct 1233 ms 50980 KB Output is correct
8 Correct 1476 ms 55808 KB Output is correct
9 Correct 2091 ms 58948 KB Output is correct
10 Correct 1049 ms 46432 KB Output is correct
11 Correct 1140 ms 48228 KB Output is correct
12 Correct 535 ms 42164 KB Output is correct
13 Correct 636 ms 39016 KB Output is correct
14 Correct 545 ms 42172 KB Output is correct
15 Correct 625 ms 39020 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 30988 KB Output is correct
2 Correct 96 ms 9844 KB Output is correct
3 Correct 659 ms 44932 KB Output is correct
4 Correct 1207 ms 50692 KB Output is correct
5 Correct 1464 ms 55824 KB Output is correct
6 Correct 2084 ms 58944 KB Output is correct
7 Correct 1034 ms 46484 KB Output is correct
8 Correct 1177 ms 50892 KB Output is correct
9 Correct 541 ms 42220 KB Output is correct
10 Correct 639 ms 38920 KB Output is correct
11 Correct 591 ms 37972 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 999 ms 49168 KB Output is correct
2 Correct 1570 ms 98548 KB Output is correct
3 Correct 1084 ms 46472 KB Output is correct
4 Correct 2080 ms 114536 KB Output is correct
5 Correct 2532 ms 130664 KB Output is correct
6 Correct 1413 ms 57524 KB Output is correct
7 Correct 1081 ms 46848 KB Output is correct
8 Correct 536 ms 38996 KB Output is correct
9 Correct 2238 ms 128476 KB Output is correct
10 Correct 1274 ms 87068 KB Output is correct
11 Correct 2156 ms 125576 KB Output is correct
12 Correct 1744 ms 102420 KB Output is correct