| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 31949 |
2017-09-18T13:32:06 Z |
minhtung0404 |
물병 (JOI14_bottle) |
C++14 |
|
243 ms |
76892 KB |
#include<bits/stdc++.h>
const int N = 2e5 + 5;
const int inf = 1e9;
using namespace std;
typedef pair <int, int> ii;
typedef pair <int, ii> iii;
vector <ii> adj[N];
priority_queue <iii, vector <iii>, greater <iii> > pq;
int n, m, p, q, x[N], y[N], dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}, lev[N], d[20][N], M[20][N];
char s[2005][2005];
int dd[2005][2005], ee[2005][2005];
struct {
int pset[N];
void init(int n) {for (int i = 1; i <= n; i++) pset[i] = i;}
int findset(int i) {return ((pset[i] == i) ? i : pset[i] = findset(pset[i]));}
void unionset(int i, int j){
if (findset(i) == findset(j)) return ;
pset[findset(i)] = findset(j);
}
} dsu;
void bfs(){
queue <ii> mq;
for (int i = 1; i <= p; i++){
mq.push(ii(x[i], y[i]));
dd[x[i]][y[i]] = 1; ee[x[i]][y[i]] = i;
}
while (mq.size()){
int xx = mq.front().first, yy = mq.front().second; mq.pop();
for (int i = 0; i < 4; i++){
int xxx = xx + dx[i], yyy = yy + dy[i];
if (xxx <= 0 || xxx > n || yyy <= 0 || yyy > m) continue;
if (s[xxx][yyy] == '#') continue;
if (dd[xxx][yyy]){
if (ee[xx][yy] != ee[xxx][yyy]) pq.push(iii(dd[xx][yy]+dd[xxx][yyy]-2, ii(ee[xxx][yyy], ee[xx][yy])));
continue;
}
dd[xxx][yyy] = dd[xx][yy] + 1; ee[xxx][yyy] = ee[xx][yy];
mq.push(ii(xxx, yyy));
}
}
}
void dfs(int u, int p){
for (int i = 0; i < int(adj[u].size()); i++){
int v = adj[u][i].first, cost = adj[u][i].second;
if (v == p) continue;
lev[v] = lev[u] + 1;
d[0][v] = u; M[0][v] = cost;
dfs(v, u);
}
}
int lca(int u, int v){
int ans = 0;
for (int i = 19; i >= 0; i--) if (lev[d[i][u]] >= lev[v]) ans = max(ans, M[i][u]), u = d[i][u];
for (int i = 19; i >= 0; i--) if (lev[d[i][v]] >= lev[u]) ans = max(ans, M[i][v]), v = d[i][v];
for (int i = 19; i >= 0; i--) {
if (d[i][u] != d[i][v]){
ans = max(ans, M[i][u]); ans = max(ans, M[i][v]);
u = d[i][u]; v = d[i][v];
}
}
if (u != v) ans = max(ans, M[0][u]), ans = max(ans, M[0][v]);
return ans;
}
int main(){
scanf("%d%d%d%d", &n, &m, &p, &q);
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%c", &s[i][j]);
for (int i = 1; i <= p; i++) scanf("%d%d", &x[i], &y[i]); bfs();
dsu.init(p);
while (pq.size()){
int cost = pq.top().first, u = pq.top().second.first, v = pq.top().second.second; pq.pop();
if (dsu.findset(u) != dsu.findset(v)) {
adj[u].push_back(ii(v, cost));
adj[v].push_back(ii(u, cost));
dsu.unionset(u, v);
}
}
for (int i = 2; i <= p; i++){
if (dsu.findset(1) != dsu.findset(i)){
adj[1].push_back(ii(i, inf));
adj[i].push_back(ii(1, inf));
dsu.unionset(1, i);
}
}
dfs(1, 1);
for (int i = 1; i < 20; i++) for (int j = 1; j <= p; j++) {
d[i][j] = d[i-1][d[i-1][j]];
M[i][j] = max(M[i-1][j], M[i-1][d[i-1][j]]);
}
while (q--){
int a, b;
scanf("%d %d", &a, &b);
int ans = lca(a, b);
ans = ((ans == inf) ? -1 : ans);
printf("%d\n", ans);
}
}
Compilation message
bottle.cpp: In function 'int main()':
bottle.cpp:73:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &n, &m, &p, &q);
^
bottle.cpp:74:84: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%c", &s[i][j]);
^
bottle.cpp:75:61: 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", &x[i], &y[i]); bfs();
^
bottle.cpp:99:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
76420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
76420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
76420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
243 ms |
76892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
