oj.uz

Submission #129837

# Submission time Handle Problem Language Result Execution time Memory
129837 2019-07-13T10:20:44 Z onjo0127 물병 (JOI14_bottle) C++11
100 / 100
 2529 ms 138576 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 8072 KB Output is correct
4 Correct 95 ms 10052 KB Output is correct
5 Correct 97 ms 9976 KB Output is correct
6 Correct 90 ms 9976 KB Output is correct
7 Correct 94 ms 10000 KB Output is correct
8 Correct 101 ms 10228 KB Output is correct
9 Correct 98 ms 10104 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 31160 KB Output is correct
2 Correct 111 ms 11384 KB Output is correct
3 Correct 839 ms 50576 KB Output is correct
4 Correct 1205 ms 54764 KB Output is correct
5 Correct 1464 ms 60012 KB Output is correct
6 Correct 828 ms 50524 KB Output is correct
7 Correct 1219 ms 54924 KB Output is correct
8 Correct 1491 ms 59788 KB Output is correct
9 Correct 2102 ms 62856 KB Output is correct
10 Correct 1025 ms 50332 KB Output is correct
11 Correct 1136 ms 52152 KB Output is correct
12 Correct 540 ms 46024 KB Output is correct
13 Correct 700 ms 42916 KB Output is correct
14 Correct 548 ms 46300 KB Output is correct
15 Correct 626 ms 42960 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 31312 KB Output is correct
2 Correct 96 ms 10256 KB Output is correct
3 Correct 643 ms 49064 KB Output is correct
4 Correct 1196 ms 54752 KB Output is correct
5 Correct 1447 ms 59896 KB Output is correct
6 Correct 2064 ms 62956 KB Output is correct
7 Correct 986 ms 50240 KB Output is correct
8 Correct 1165 ms 54792 KB Output is correct
9 Correct 539 ms 46168 KB Output is correct
10 Correct 624 ms 43048 KB Output is correct
11 Correct 584 ms 42072 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 998 ms 54688 KB Output is correct
2 Correct 1610 ms 106636 KB Output is correct
3 Correct 1061 ms 50360 KB Output is correct
4 Correct 2001 ms 122420 KB Output is correct
5 Correct 2529 ms 138576 KB Output is correct
6 Correct 1449 ms 62712 KB Output is correct
7 Correct 1132 ms 50456 KB Output is correct
8 Correct 511 ms 42624 KB Output is correct
9 Correct 2249 ms 136508 KB Output is correct
10 Correct 1178 ms 95056 KB Output is correct
11 Correct 2191 ms 133400 KB Output is correct
12 Correct 1718 ms 110024 KB Output is correct