oj.uz

Submission #18532

# Submission time Handle Problem Language Result Execution time Memory
18532 2016-02-08T05:27:51 Z choyi0521 물병 (JOI14_bottle) C++14
100 / 100
 1702 ms 377936 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];
	uf(){
		for (int i = 1; i <= MAX_P; i++)
			par[i] = i;
	}
	int find(int x) {
		if (x == par[x]) return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		par[y] = x;
	}
}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 72012 KB Output is correct
2 Correct 4 ms 72028 KB Output is correct
3 Correct 7 ms 72600 KB Output is correct
4 Correct 102 ms 72604 KB Output is correct
5 Correct 113 ms 72612 KB Output is correct
6 Correct 95 ms 72596 KB Output is correct
7 Correct 84 ms 72576 KB Output is correct
8 Correct 107 ms 73800 KB Output is correct
9 Correct 83 ms 72536 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 76428 KB Output is correct
2 Correct 69 ms 82280 KB Output is correct
3 Correct 596 ms 147476 KB Output is correct
4 Correct 880 ms 225108 KB Output is correct
5 Correct 1026 ms 227400 KB Output is correct
6 Correct 608 ms 147476 KB Output is correct
7 Correct 869 ms 224984 KB Output is correct
8 Correct 1043 ms 227440 KB Output is correct
9 Correct 1407 ms 377936 KB Output is correct
10 Correct 791 ms 220908 KB Output is correct
11 Correct 811 ms 222808 KB Output is correct
12 Correct 367 ms 148644 KB Output is correct
13 Correct 450 ms 146044 KB Output is correct
14 Correct 372 ms 148632 KB Output is correct
15 Correct 435 ms 146040 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 76432 KB Output is correct
2 Correct 55 ms 81304 KB Output is correct
3 Correct 421 ms 145632 KB Output is correct
4 Correct 874 ms 225012 KB Output is correct
5 Correct 1070 ms 227412 KB Output is correct
6 Correct 1447 ms 377824 KB Output is correct
7 Correct 798 ms 220788 KB Output is correct
8 Correct 830 ms 224740 KB Output is correct
9 Correct 386 ms 148644 KB Output is correct
10 Correct 472 ms 146040 KB Output is correct
11 Correct 344 ms 108880 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 758 ms 148780 KB Output is correct
2 Correct 1115 ms 174820 KB Output is correct
3 Correct 826 ms 220920 KB Output is correct
4 Correct 1402 ms 257628 KB Output is correct
5 Correct 1702 ms 268444 KB Output is correct
6 Correct 1063 ms 230364 KB Output is correct
7 Correct 792 ms 220912 KB Output is correct
8 Correct 354 ms 146152 KB Output is correct
9 Correct 1437 ms 265452 KB Output is correct
10 Correct 1048 ms 168388 KB Output is correct
11 Correct 1561 ms 262048 KB Output is correct
12 Correct 1336 ms 250528 KB Output is correct