| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 18529 |
2016-02-08T05:25:17 Z |
choyi0521 |
물병 (JOI14_bottle) |
C++14 |
|
695 ms |
149560 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(!ck[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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
72792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
77208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
77212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
695 ms |
149560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
