oj.uz

Submission #18530

# Submission time Handle Problem Language Result Execution time Memory
18530 2016-02-08T05:25:39 Z choyi0521 물병 (JOI14_bottle) C++14
60 / 100
 1421 ms 378716 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;
};
struct edge {
	int x, y,d;
	bool operator<(edge i) const {
		return d < i. d;
	}
};
vector<edge> e;
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]) {
			e.push_back({ ck[he.x][he.y],he.idx,dist[he.x][he.y] + he.dis - 1 });
			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 });
	}
	sort(e.begin(), e.end());
	for (auto it : e) {
		int rx = st.find(it.x), ry = st.find(it.y);
		if (rx == ry) continue;
		adj[it.x].push_back({ it.y,it.d });
		adj[it.y].push_back({ it.x,it.d });
		st.unite(rx, ry);
	}
	for (int i = 1; i <= p; i++)
		if(!dck[i]) dfs(1);
	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 Correct 7 ms 72792 KB Output is correct
2 Correct 0 ms 72808 KB Output is correct
3 Correct 10 ms 73380 KB Output is correct
4 Incorrect 104 ms 73384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 77208 KB Output is correct
2 Correct 72 ms 83060 KB Output is correct
3 Correct 613 ms 148256 KB Output is correct
4 Correct 898 ms 225888 KB Output is correct
5 Correct 1058 ms 228180 KB Output is correct
6 Correct 577 ms 148256 KB Output is correct
7 Correct 868 ms 225764 KB Output is correct
8 Correct 1051 ms 228220 KB Output is correct
9 Correct 1420 ms 378716 KB Output is correct
10 Correct 775 ms 221688 KB Output is correct
11 Correct 847 ms 223588 KB Output is correct
12 Correct 388 ms 149424 KB Output is correct
13 Correct 453 ms 146824 KB Output is correct
14 Correct 354 ms 149412 KB Output is correct
15 Correct 453 ms 146820 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 77212 KB Output is correct
2 Correct 64 ms 82084 KB Output is correct
3 Correct 434 ms 146412 KB Output is correct
4 Correct 874 ms 225792 KB Output is correct
5 Correct 1029 ms 228192 KB Output is correct
6 Correct 1421 ms 378604 KB Output is correct
7 Correct 795 ms 221568 KB Output is correct
8 Correct 850 ms 225520 KB Output is correct
9 Correct 386 ms 149424 KB Output is correct
10 Correct 464 ms 146820 KB Output is correct
11 Correct 340 ms 109660 KB Output is correct

Subtask #4
0.0 / 30.0

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