| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 129697 |
2019-07-13T04:59:01 Z |
임유진(#3141) |
물병 (JOI14_bottle) |
C++14 |
|
478 ms |
53852 KB |
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXH 2005
#define MAXP 200005
#define fi first
#define se second
typedef pair<int, int> pii;
struct edge {
int A, B, D;
} ed[8000005];
const int mm[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
char m[MAXH][MAXH];
pii bui[MAXP], que[MAXP];
queue<pii> q;
int dis[MAXH][MAXH], fro[MAXH][MAXH];
int en;
int uni[MAXP];
vector<pii> mst[MAXP];
pii par[20][MAXP];
int dep[MAXP];
bool chk[MAXP];
int guni(int x) { return x == uni[x] ? x : uni[x] = guni(uni[x]); }
void unite(int x, int y) { uni[guni(x)] = guni(y); }
void dfs(int x) {
//printf("dfs(%d)\n", x);
chk[x] = true;
for(auto a : mst[x]) if(!chk[a.se]) {
par[0][a.se] = make_pair(a.fi, x);
dep[a.se] = dep[x] + 1;
dfs(a.se);
}
}
int lcad(int x, int y) {
int ans = 0;
if(dep[x] < dep[y]) swap(x, y);
for(int i = 0; i < 20; i++) if((dep[x] - dep[y]) & (1 << i)) {
ans = max(ans, par[i][x].fi);
x = par[i][x].se;
}
if(x == y) return ans;
for(int i = 19; i >= 0; i--) if(par[i][x].se != par[i][y].se) {
ans = max(ans, max(par[i][x].fi, par[i][y].fi));
x = par[i][x].se;
y = par[i][y].se;
}
return max(ans, max(par[0][x].fi, par[0][y].fi));
}
int main() {
int H, W, P, Q;
//freopen("input.txt", "r", stdin);
scanf("%d%d%d%d", &H, &W, &P, &Q);
for(int i = 1; i <= H; i++) scanf("%s", m[i] + 1);
for(int i = 1; i <= P; i++) scanf("%d%d", &bui[i].fi, &bui[i].se);
for(int i = 0; i < Q; i++) scanf("%d%d", &que[i].fi, &que[i].se);
for(int i = 1; i <= H; i++) m[i][0] = m[i][W + 1] = '#';
for(int i = 1; i <= W; i++) m[0][i] = m[H + 1][i] = '#';
for(int i = 1; i <= P; i++) {
fro[bui[i].fi][bui[i].se] = i;
q.push(bui[i]);
}
while(!q.empty()) {
pii t = q.front();
q.pop();
for(int i = 0; i < 4; i++) {
int a = t.fi + mm[i][0], b = t.se + mm[i][1];
if(fro[a][b] == 0 && m[a][b] == '.') {
fro[a][b] = fro[t.fi][t.se];
dis[a][b] = dis[t.fi][t.se] + 1;
q.push(make_pair(a, b));
}
}
}
/*
for(int i = 1; i <= H; i++) {
for(int j = 1; j <= W; j++) printf("(%d, %d)", dis[i][j], fro[i][j]);
printf("\n");
}
*/
for(int i = 1; i <= H; i++) for(int j = 1; j < W; j++)
if(fro[i][j + 1] != 0 && fro[i][j] != fro[i][j + 1])
ed[en++] = (edge) { fro[i][j], fro[i][j + 1], dis[i][j] + dis[i][j + 1] };
for(int i = 1; i < H; i++) for(int j = 1; j <= W; j++)
if(fro[i][j] != 0 && fro[i + 1][j] != 0 && fro[i][j] != fro[i + 1][j])
ed[en++] = (edge) { fro[i][j], fro[i + 1][j], dis[i][j] + dis[i + 1][j] };
//for(int i = 0; i < en; i++) printf("[%d %d %d]\n", ed[i].A, ed[i].B, ed[i].D);
sort(ed, ed + en, [&](edge a, edge b) { return a.D < b.D; } );
for(int i = 1; i <= P; i++) uni[i] = i;
for(int i = 0; i < en; i++) if(guni(ed[i].A) != guni(ed[i].B)) {
unite(ed[i].A, ed[i].B);
mst[ed[i].A].push_back(make_pair(ed[i].D, ed[i].B));
mst[ed[i].B].push_back(make_pair(ed[i].D, ed[i].A));
}
/*
for(int i = 1; i <= P; i++) {
for(auto a : mst[i]) printf("(%d, %d)", a.fi, a.se);
printf("\n");
}
*/
for(int i = 1; i <= P; i++) if(!chk[i]) {
par[0][i].se = i;
dfs(i);
}
/*
for(int i = 1; i <= P; i++) printf("(%d, %d)", par[0][i].fi, par[0][i].se);
printf("\n");
*/
for(int i = 1; i < 20; i++) for(int j = 1; j <= P; j++)
par[i][j] = make_pair(max(par[i - 1][j].fi, par[i - 1][par[i - 1][j].se].fi), par[i - 1][par[i - 1][j].se].se);
//printf("*\n");
for(int i = 0; i < Q; i++) printf("%d\n", guni(que[i].fi) == guni(que[i].se) ? lcad(que[i].fi, que[i].se) : -1);
return 0;
}
Compilation message
bottle.cpp: In function 'int main()':
bottle.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &H, &W, &P, &Q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:66:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i <= H; i++) scanf("%s", m[i] + 1);
~~~~~^~~~~~~~~~~~~~~~
bottle.cpp:67:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i <= P; i++) scanf("%d%d", &bui[i].fi, &bui[i].se);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:68:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 0; i < Q; i++) scanf("%d%d", &que[i].fi, &que[i].se);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
6008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
27512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
27516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
478 ms |
53852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
