| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 129690 |
2019-07-13T04:49:52 Z |
이온조(#3139) |
물병 (JOI14_bottle) |
C++14 |
|
788 ms |
47652 KB |
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0, 0};
const int _N = 200009;
vector<pii> adj[_N];
int A[_N], B[_N], D[2009][2009], um[2009][2009], U[_N], p[22][_N], mx[22][_N], l, in[_N], ou[_N], t;
bool vs[2009][2009];
char S[2009][2009];
int root(int x) {
if(U[x] == x) return x;
return U[x] = root(U[x]);
}
void merg(int u, int v, int w) {
u = root(u); v = root(v);
if(u != v) {
// printf("%d <--> %d, cost: %d\n", u, v, w);
adj[u].push_back({v, w});
adj[v].push_back({u, w});
U[u] = v;
}
}
bool isup(int u, int v) {
return in[u] <= in[v] && ou[u] >= ou[v];
}
int get(int u, int v) {
// printf("get: u: %d, v: %d\n", u, v);
int ret = 0;
if(isup(u, v)) swap(u, v);
if(!isup(v, u)) {
for(int i=l; i>=0; i--) {
if(!isup(p[i][v], u)) {
ret = max(ret, mx[i][v]);
v = p[i][v];
}
}
ret = max(ret, mx[0][v]);
v = p[0][v];
}
assert(isup(v, u));
for(int i=l; i>=0; i--) if(!isup(p[i][u], v) || p[i][u] == v) {
ret = max(ret, mx[i][u]);
u = p[i][u];
}
return ret;
}
void dfs(int x, int p, int w) {
printf("dfs: x: %d, p: %d, w: %d\n", x, p, w);
in[x] = ++t; ::p[0][x] = p; mx[0][x] = w;
for(auto& it: adj[x]) if(it.first != p) dfs(it.first, x, it.second);
ou[x] = t;
}
int main() {
int H, W, P, Q; scanf("%d%d%d%d",&H,&W,&P,&Q);
for(int i=0; i<=H+1; i++) for(int j=0; j<=W+1; j++) S[i][j] = '#';
for(int i=1; i<=H; i++) {
for(int j=1; j<=W; j++) {
scanf(" %c",&S[i][j]);
}
}
queue<tiii> que;
for(int i=1; i<=P; i++) {
scanf("%d%d",&A[i],&B[i]);
que.push((tiii){A[i], B[i], i});
vs[A[i]][B[i]] = 1;
um[A[i]][B[i]] = i;
U[i] = i;
}
while(que.size()) {
int x, y, id; tie(x, y, id) = que.front(); que.pop();
for(int k=0; k<4; k++) {
int X = x+dx[k], Y = y+dy[k];
if(!vs[X][Y] && S[X][Y] != '#') {
vs[X][Y] = 1;
D[X][Y] = D[x][y] + 1;
um[X][Y] = id;
que.push((tiii){X, Y, id});
}
else {
if(S[X][Y] == '#') continue;
merg(id, um[X][Y], D[x][y] + D[X][Y]);
}
}
}
for(int i=1; i<=P; i++) if(p[0][i] == 0) dfs(i, i, 0);
for(int i=1; (1<<i)<=P; i++) {
for(int j=1; j<=P; j++) {
p[i][j] = p[i-1][p[i-1][j]];
mx[i][j] = max(mx[i-1][j], mx[i-1][p[i-1][j]]);
}
l = i;
}
printf("l: %d\n", l);
while(Q--) {
int S, T; scanf("%d%d",&S,&T);
if(root(S) != root(T)) puts("-1");
else printf("%d\n", get(S, T));
}
return 0;
}
Compilation message
bottle.cpp: In function 'int main()':
bottle.cpp:64:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int H, W, P, Q; scanf("%d%d%d%d",&H,&W,&P,&Q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:68:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c",&S[i][j]);
~~~~~^~~~~~~~~~~~~~~~
bottle.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&A[i],&B[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~
bottle.cpp:105:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int S, T; scanf("%d%d",&S,&T);
~~~~~^~~~~~~~~~~~~~
| # |
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 |
58 ms |
30840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
30844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
788 ms |
47652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
