oj.uz

Submission #43280

# Submission time Handle Problem Language Result Execution time Memory
43280 2018-03-13T03:52:36 Z smu201111192 물병 (JOI14_bottle) C++14
100 / 100
 3446 ms 366732 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 129192 KB Output is correct
2 Correct 380 ms 130060 KB Output is correct
3 Correct 358 ms 130096 KB Output is correct
4 Correct 459 ms 146004 KB Output is correct
5 Correct 471 ms 147544 KB Output is correct
6 Correct 463 ms 148776 KB Output is correct
7 Correct 460 ms 150132 KB Output is correct
8 Correct 507 ms 152896 KB Output is correct
9 Correct 439 ms 152896 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 152896 KB Output is correct
2 Correct 491 ms 152896 KB Output is correct
3 Correct 870 ms 162500 KB Output is correct
4 Correct 1132 ms 168340 KB Output is correct
5 Correct 1316 ms 174664 KB Output is correct
6 Correct 879 ms 174664 KB Output is correct
7 Correct 1146 ms 180336 KB Output is correct
8 Correct 1304 ms 186552 KB Output is correct
9 Correct 1483 ms 193800 KB Output is correct
10 Correct 890 ms 193800 KB Output is correct
11 Correct 1075 ms 195220 KB Output is correct
12 Correct 703 ms 196688 KB Output is correct
13 Correct 654 ms 198624 KB Output is correct
14 Correct 717 ms 204612 KB Output is correct
15 Correct 663 ms 206504 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 206504 KB Output is correct
2 Correct 453 ms 206504 KB Output is correct
3 Correct 773 ms 214852 KB Output is correct
4 Correct 1196 ms 221716 KB Output is correct
5 Correct 1359 ms 228072 KB Output is correct
6 Correct 1574 ms 235600 KB Output is correct
7 Correct 1077 ms 235600 KB Output is correct
8 Correct 1170 ms 237872 KB Output is correct
9 Correct 742 ms 238668 KB Output is correct
10 Correct 676 ms 240384 KB Output is correct
11 Correct 658 ms 243684 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1100 ms 271664 KB Output is correct
2 Correct 1869 ms 293220 KB Output is correct
3 Correct 944 ms 293220 KB Output is correct
4 Correct 2539 ms 315812 KB Output is correct
5 Correct 3280 ms 334588 KB Output is correct
6 Correct 1478 ms 334588 KB Output is correct
7 Correct 899 ms 334588 KB Output is correct
8 Correct 627 ms 334588 KB Output is correct
9 Correct 3446 ms 362944 KB Output is correct
10 Correct 1258 ms 362944 KB Output is correct
11 Correct 2619 ms 366732 KB Output is correct
12 Correct 1868 ms 366732 KB Output is correct