Submission #43280

#	Time	Username	Problem	Language	Result	Execution time	Memory
43280		smu201111192	물병 (JOI14_bottle)	C++14	100 / 100	3446 ms	366732 KiB

bottle

#include <iostream>
#include <cstdio>
#include <cassert>
#include <bitset>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
using namespace std;
const int MAXN = 4100005;
const int MAXQ = 400005;
int r,c,p,q;
string board[2005];
const int dy[4] = {0,0,1,-1};
const int dx[4] = {1,-1,0,0};
int yy[MAXQ],xx[MAXQ],qu[MAXQ],qv[MAXQ],lo[MAXQ],hi[MAXQ];
int dist[2005][2005];
vector<int> query[MAXN];
int dom[2005][2005],parent[MAXN];
int find(int u){
    return u == parent[u] ? u : parent[u] = find(parent[u]);
}
void mrg(int u,int v){
    u = find(u);
    v = find(v);
    if(u == v)return;
    parent[u] = v;
}
bool isCan(int y,int x){
    return  y>= 0 && y <r && x>=0 && x<c && board[y][x] !='#';
}
void bfs(){
    queue<pair<int,int> > q;
    memset(dist,0,sizeof(dist));
    for(int i = 0; i < r; i++) for(int j = 0; j <c ; j++){
        if(dom[i][j]){
            q.push(make_pair(i,j));
        }
    }
    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        for(int k = 0; k <4; k++){
            int ny = y + dy[k];
            int nx = x + dx[k];
            if(isCan(ny,nx) && !dom[ny][nx]){
                q.push({ny,nx});
                dom[ny][nx] = dom[y][x];
                dist[ny][nx] = dist[y][x] + 1;
            }
        }
    }
}
struct edge{
    int u,v,w;
    bool operator < (const edge e)const{
        return w < e.w;
    }
};
vector<edge> ev;
void init(){
    for(int i = 0; i < MAXN; i++) parent[i] = i;
    for(int i = 0; i < MAXN; i++) query[i].clear();
}
bool pbs(){
    int update = 0;
    init();
    for(int i = 1; i <= q; i++){
        int mid = (lo[i] + hi[i]) / 2;
        if(lo[i] <= hi[i]){
            query[mid].push_back(i);
            update = 1;
        }
    }
    for(int i = 0; i < ev.size(); i++){
        mrg(ev[i].u,ev[i].v);
        for(auto x : query[i]){
            int u = qu[x];
            int v = qv[x];
            if(find(u) == find(v))
                hi[x] = i - 1;
            else lo[x] = i + 1;
        }
    }
    return update;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> r >> c>> p >> q;
    for(int i = 0 ; i < r; i++) cin >> board[i];
    for(int i = 1 ; i <= p; i++){
        cin >> yy[i] >> xx[i];
        yy[i]--; xx[i]--;
        dom[yy[i]][xx[i]] = i;
    }
    for(int i = 1; i <= q; i++){
        cin >> qu[i] >> qv[i];
    }
    bfs();
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            if(!isCan(i,j)) continue;
            int y = i;
            int x = j;
            for(int k = 0; k < 4; k++){
                int ny = y + dy[k];
                int nx = x + dx[k];
                if(isCan(ny,nx) && dom[y][x] != dom[ny][nx]){
                    ev.push_back({dom[y][x],dom[ny][nx],dist[y][x] + dist[ny][nx]});
                }
            }
        }
    }
    sort(ev.begin(),ev.end());
    for(int i = 1; i <= q; i++){
        lo[i] = 0;
        hi[i] = ev.size() - 1;
    }
    while(pbs());
    for(int i = 1; i <= q; i++){
        int piv = hi[i]  + 1;
        if(piv >= ev.size()) cout<<-1<<"\n";
        else cout<<ev[piv].w<<"\n";
    }
    return 0;
}

Compilation message (stderr)

bottle.cpp: In function 'bool pbs()':
bottle.cpp:87:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ev.size(); i++){
                      ^
bottle.cpp: In function 'int main()':
bottle.cpp:135:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(piv >= ev.size()) cout<<-1<<"\n";
                ^

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30