oj.uz

Submission #18533

# Submission time Handle Problem Language Result Execution time Memory
18533 2016-02-08T05:39:27 Z choyi0521 물병 (JOI14_bottle) C++14
30 / 100
 846 ms 83832 KB 
#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_P = 200000, LGP=17;
const int fx[] = { 1,0,-1,0 }, fy[] = { 0,1,0,-1 };
int h, w,p,q, ck[2001][2001],dist[2001][2001];
char map[2001][2002];
vector<pair<int, int>> adj[MAX_P+1];
struct uf {
	int par[MAX_P+1],rnk[MAX_P+1];
	uf(){
		for (int i = 1; i <= MAX_P; i++)
			par[i] = i, rnk[i] = 0;
	}
	int find(int x) {
		if (x == par[x]) return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		if (rnk[x] > rnk[y]) par[y] = x;
		else {
			par[x] = y;
			if (rnk[x] == rnk[y]) rnk[y]++;
		}
	}
}st;
struct qst {
	int x, y,idx,dis;
};
bool dck[MAX_P + 1];
int dp[MAX_P + 1][LGP + 1],maxi[MAX_P+1][LGP+1],lv[MAX_P+1];
void dfs(int h) {
	dck[h] = true;
	for (auto t : adj[h]) {
		if (dck[t.first]) continue;
		lv[t.first] = lv[h] + 1;
		dp[t.first][0] = h;
		maxi[t.first][0] = t.second;
		for (int i = 1; i <= LGP; i++) {
			dp[t.first][i] = dp[dp[t.first][i - 1]][i - 1];
			maxi[t.first][i] = max(maxi[dp[t.first][i - 1]][i - 1], maxi[t.first][i - 1]);
		}
		dfs(t.first);
	}
}
int lca(int x, int y) {
	if (lv[x] < lv[y]) swap(x, y);
	int res = 0;
	for (int i = LGP; i >= 0; i--)
		if (lv[x] - lv[y] >= 1 << i) res = max(res, maxi[x][i]),x = dp[x][i];
	if (x == y) return res;
	for (int i = LGP; i >= 0; i--) {
		if (dp[x][i] != dp[y][i]) {
			res = max({ res,maxi[x][i],maxi[y][i] });
			x = dp[x][i];
			y = dp[y][i];
		}
	}
	return max({ res,maxi[x][0],maxi[y][0] });
}
int main() {
	scanf("%d %d %d %d", &h, &w, &p, &q);
	for (int i = 1; i <= h; i++) scanf("%s", map[i] + 1);
	queue<qst> que;
	for (int i = 1; i <= p; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		que.push({ x,y,i,0 });
	}
	while (!que.empty()) {
		qst he = que.front();
		que.pop();
		if (he.x<1 || he.y<1 || he.x>h || he.y>w || map[he.x][he.y]=='#') continue;
		if (ck[he.x][he.y]) {
			int a = st.find(ck[he.x][he.y]),b=st.find(he.idx),
				d=dist[he.x][he.y]+he.dis-1;
			if (a != b) {
				adj[ck[he.x][he.y]].push_back({ he.idx,d });
				adj[he.idx].push_back({ ck[he.x][he.y],d });
				st.unite(a, b);
			}
			continue;
		}
		ck[he.x][he.y] = he.idx;
		dist[he.x][he.y] = he.dis;
		for (int i = 0; i < 4; i++)
			que.push({ he.x + fx[i],he.y + fy[i],he.idx,he.dis + 1 });
	}
	for (int i = 1; i <= p; i++)
		if(!dck[i]) dfs(i);
	for (int i = 0; i < q; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		if (st.find(x) != st.find(y)) puts("-1");
		else printf("%d\n", lca(x, y));
	}
	return 0;
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 72124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 72652 KB Output is correct
2 Correct 58 ms 74012 KB Output is correct
3 Correct 509 ms 74664 KB Output is correct
4 Correct 656 ms 78652 KB Output is correct
5 Correct 733 ms 80840 KB Output is correct
6 Correct 506 ms 74656 KB Output is correct
7 Correct 666 ms 78388 KB Output is correct
8 Correct 749 ms 80840 KB Output is correct
9 Correct 846 ms 83832 KB Output is correct
10 Correct 578 ms 74232 KB Output is correct
11 Correct 610 ms 76132 KB Output is correct
12 Correct 244 ms 75780 KB Output is correct
13 Correct 303 ms 73176 KB Output is correct
14 Correct 249 ms 75776 KB Output is correct
15 Correct 295 ms 73288 KB Output is correct

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 72652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 614 ms 76004 KB Output isn't correct
2 Halted 0 ms 0 KB -