oj.uz

Submission #43282

# Submission time Handle Problem Language Result Execution time Memory
43282 2018-03-13T03:59:29 Z smu201111192 물병 (JOI14_bottle) C++14
10 / 100
 899 ms 125820 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 = 400005;
const int MAXQ = 400005;
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],r,c,p,q,dist[2005][2005],dom[2005][2005],parent[MAXQ];
vector<int> query[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:84: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:132: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 39 ms 27640 KB Output is correct
2 Correct 40 ms 28232 KB Output is correct
3 Correct 41 ms 28440 KB Output is correct
4 Correct 147 ms 43140 KB Output is correct
5 Correct 150 ms 43260 KB Output is correct
6 Correct 141 ms 43260 KB Output is correct
7 Correct 158 ms 43260 KB Output is correct
8 Correct 175 ms 44348 KB Output is correct
9 Correct 147 ms 44348 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 44348 KB Output is correct
2 Correct 114 ms 44348 KB Output is correct
3 Correct 533 ms 47876 KB Output is correct
4 Correct 745 ms 50104 KB Output is correct
5 Correct 899 ms 52092 KB Output is correct
6 Correct 552 ms 52092 KB Output is correct
7 Correct 753 ms 52092 KB Output is correct
8 Correct 862 ms 52420 KB Output is correct
9 Runtime error 856 ms 110624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 110624 KB Output is correct
2 Correct 88 ms 110624 KB Output is correct
3 Correct 421 ms 110624 KB Output is correct
4 Correct 728 ms 110624 KB Output is correct
5 Correct 889 ms 110624 KB Output is correct
6 Runtime error 870 ms 113644 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 761 ms 122080 KB Output is correct
2 Runtime error 709 ms 125820 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -