| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 594862 |
2022-07-13T05:36:14 Z |
반딧불(#8437) |
물병 (JOI14_bottle) |
C++14 |
|
591 ms |
73148 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int xx[]={0, 1, 0, -1}, yy[]={1, 0, -1, 0};
struct unionFind{
int par[200002];
unionFind(){}
void init(int n){
for(int i=0; i<=n; i++){
par[i] = i;
}
}
int find(int x){
if(x == par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int x, int y){
x = par[x], y = par[y];
par[x] = y;
}
} dsu;
struct dat{
int x, y, d, id;
dat(){}
dat(int x, int y, int d, int id): x(x), y(y), d(d), id(id){}
};
struct Edge{
int x, y, d;
Edge(){}
Edge(int x, int y, int d): x(x), y(y), d(d){}
bool operator<(const Edge &r)const{
return d<r.d;
}
};
int n, m, k, q;
char board[2002][2002];
int num[2002][2002];
int px[200002], py[200002];
int dist[2002][2002];
int vnum[2002][2002];
int ans[200002];
vector<Edge> edges;
void makeEdges(){
vector<dat> que;
for(int i=1; i<=k; i++){
int x = px[i], y = py[i];
que.push_back(dat(x, y, 0, i));
dist[x][y] = 0;
vnum[x][y] = i;
}
while(!que.empty()){
int len = que.front().d;
vector<dat> nqueue;
vector<Edge> waitlist;
while(!que.empty()){
dat tmp = que.back(); que.pop_back();
int x = tmp.x, y = tmp.y;
// printf("(%d, %d, %d, %d)\n", x, y, len, tmp.id);
for(int d=0; d<4; d++){
int tx = x+xx[d], ty = y+yy[d];
if(tx<1 || tx>n || ty<1 || ty>m || board[tx][ty]=='#' || dist[tx][ty]<len) continue;
if(dist[tx][ty] == 1e9){
dist[tx][ty] = len+1;
vnum[tx][ty] = tmp.id;
nqueue.push_back(dat(tx, ty, len+1, tmp.id));
}
else if(!vnum[tx][ty]) continue;
else{ /// �ٷ� ���� ��
int vx = tmp.id, vy = vnum[tx][ty];
if(dsu.find(vx) == dsu.find(vy)) continue;
if(dist[tx][ty] == len){
dsu.merge(vx, vy);
edges.push_back(Edge(vx, vy, len*2));
}
else{
assert(dist[tx][ty] == len+1);
waitlist.push_back(Edge(vx, vy, len*2+1));
}
}
}
}
for(Edge edge: waitlist){
if(dsu.find(edge.x) == dsu.find(edge.y)) continue;
dsu.merge(edge.x, edge.y);
edges.push_back(Edge(edge.x, edge.y, edge.d));
}
que.swap(nqueue);
}
}
int ql[200002], qr[200002];
int pbsL[200002], pbsR[200002], pbsMid[200002], pbsAns[200002];
vector<int> pbsVec[200002];
int pbsDone;
int main(){
scanf("%d %d %d %d", &n, &m, &k, &q);
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
scanf(" %c", &board[i][j]);
num[i][j] = (i-1)*m+j;
dist[i][j] = 1e9;
}
for(int i=1; i<=k; i++){
scanf("%d %d", &px[i], &py[i]);
board[px[i]][py[i]] = 'b';
dist[px[i]][py[i]] = 0;
}
dsu.init(k);
makeEdges();
int s = (int)edges.size();
for(int i=1; i<=q; i++){
scanf("%d %d", &ql[i], &qr[i]);
pbsL[i] = 0, pbsR[i] = s-1, pbsAns[i] = s;
if(pbsL[i] > pbsR[i]) pbsDone++;
}
while(pbsDone < q){
for(int i=0; i<s; i++) pbsVec[i].clear();
for(int i=1; i<=q; i++){
if(pbsL[i] > pbsR[i]) continue;
pbsMid[i] = (pbsL[i] + pbsR[i]) / 2;
pbsVec[pbsMid[i]].push_back(i);
}
dsu.init(k);
for(int i=0; i<s; i++){
dsu.merge(edges[i].x, edges[i].y);
for(auto x: pbsVec[i]){
if(dsu.find(ql[x]) == dsu.find(qr[x])){
pbsAns[x] = i;
pbsR[x] = i-1;
}
else pbsL[x] = i+1;
if(pbsL[x] > pbsR[x]) pbsDone++;
}
}
}
for(int i=1; i<=q; i++){
if(pbsAns[i] == s) puts("-1");
else printf("%d\n", edges[pbsAns[i]].d);
}
}
Compilation message
bottle.cpp: In function 'int main()':
bottle.cpp:110:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
110 | scanf("%d %d %d %d", &n, &m, &k, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:112:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | scanf(" %c", &board[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
bottle.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | scanf("%d %d", &px[i], &py[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
127 | scanf("%d %d", &ql[i], &qr[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
6100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
35732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
35788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
591 ms |
73148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
