oj.uz

Submission #18528

# Submission time Handle Problem Language Result Execution time Memory
18528 2016-02-08T05:19:03 Z choyi0521 물병 (JOI14_bottle) C++14
60 / 100
 745 ms 102200 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]) {
			if (ck[he.x][he.y] != he.idx)
				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);
	}
	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 3 ms 72300 KB Output is correct
2 Correct 6 ms 72412 KB Output is correct
3 Correct 6 ms 72268 KB Output is correct
4 Incorrect 91 ms 72272 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 32 ms 73136 KB Output is correct
2 Correct 50 ms 76208 KB Output is correct
3 Correct 407 ms 75168 KB Output is correct
4 Correct 552 ms 83024 KB Output is correct
5 Correct 623 ms 89888 KB Output is correct
6 Correct 409 ms 75168 KB Output is correct
7 Correct 540 ms 82848 KB Output is correct
8 Correct 628 ms 89976 KB Output is correct
9 Correct 732 ms 102048 KB Output is correct
10 Correct 473 ms 76560 KB Output is correct
11 Correct 509 ms 78380 KB Output is correct
12 Correct 243 ms 80256 KB Output is correct
13 Correct 297 ms 74056 KB Output is correct
14 Correct 214 ms 80192 KB Output is correct
15 Correct 305 ms 74040 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 73204 KB Output is correct
2 Correct 39 ms 73500 KB Output is correct
3 Correct 283 ms 72784 KB Output is correct
4 Correct 539 ms 82932 KB Output is correct
5 Correct 628 ms 89948 KB Output is correct
6 Correct 745 ms 102200 KB Output is correct
7 Correct 479 ms 76440 KB Output is correct
8 Correct 537 ms 82688 KB Output is correct
9 Correct 261 ms 80252 KB Output is correct
10 Correct 291 ms 74040 KB Output is correct
11 Correct 262 ms 72784 KB Output is correct

Subtask #4
0.0 / 30.0

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