oj.uz

Submission #18531

# Submission time Handle Problem Language Result Execution time Memory
18531 2016-02-08T05:26:11 Z choyi0521 물병 (JOI14_bottle) C++14
100 / 100
 1590 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(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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 72792 KB Output is correct
2 Correct 9 ms 72808 KB Output is correct
3 Correct 8 ms 73380 KB Output is correct
4 Correct 101 ms 73384 KB Output is correct
5 Correct 94 ms 73392 KB Output is correct
6 Correct 90 ms 73376 KB Output is correct
7 Correct 97 ms 73356 KB Output is correct
8 Correct 109 ms 74580 KB Output is correct
9 Correct 72 ms 73316 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 77208 KB Output is correct
2 Correct 82 ms 83060 KB Output is correct
3 Correct 610 ms 148256 KB Output is correct
4 Correct 849 ms 225888 KB Output is correct
5 Correct 1055 ms 228180 KB Output is correct
6 Correct 602 ms 148256 KB Output is correct
7 Correct 881 ms 225764 KB Output is correct
8 Correct 1054 ms 228220 KB Output is correct
9 Correct 1445 ms 378716 KB Output is correct
10 Correct 786 ms 221688 KB Output is correct
11 Correct 842 ms 223588 KB Output is correct
12 Correct 367 ms 149424 KB Output is correct
13 Correct 431 ms 146824 KB Output is correct
14 Correct 390 ms 149412 KB Output is correct
15 Correct 444 ms 146820 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 77212 KB Output is correct
2 Correct 66 ms 82084 KB Output is correct
3 Correct 432 ms 146412 KB Output is correct
4 Correct 854 ms 225792 KB Output is correct
5 Correct 1042 ms 228192 KB Output is correct
6 Correct 1412 ms 378604 KB Output is correct
7 Correct 799 ms 221568 KB Output is correct
8 Correct 812 ms 225520 KB Output is correct
9 Correct 401 ms 149424 KB Output is correct
10 Correct 472 ms 146820 KB Output is correct
11 Correct 346 ms 109660 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 731 ms 149560 KB Output is correct
2 Correct 1110 ms 175600 KB Output is correct
3 Correct 813 ms 221700 KB Output is correct
4 Correct 1411 ms 258408 KB Output is correct
5 Correct 1590 ms 269224 KB Output is correct
6 Correct 1035 ms 231144 KB Output is correct
7 Correct 793 ms 221692 KB Output is correct
8 Correct 373 ms 146932 KB Output is correct
9 Correct 1420 ms 266232 KB Output is correct
10 Correct 1030 ms 169168 KB Output is correct
11 Correct 1502 ms 262828 KB Output is correct
12 Correct 1295 ms 251308 KB Output is correct