oj.uz

Submission #43281

# Submission time Handle Problem Language Result Execution time Memory
43281 2018-03-13T03:59:08 Z smu201111192 물병 (JOI14_bottle) C++14
70 / 100
 2383 ms 237336 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 = 2000005;
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";
                ^
bottle.cpp: In function 'void init()':
bottle.cpp:71:48: warning: iteration 400005u invokes undefined behavior [-Waggressive-loop-optimizations]
     for(int i = 0; i < MAXN; i++) parent[i] = i;
                                                ^
bottle.cpp:71:22: note: containing loop
     for(int i = 0; i < MAXN; i++) parent[i] = i;
                      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 71160 KB Output is correct
2 Correct 189 ms 71416 KB Output is correct
3 Correct 183 ms 71416 KB Output is correct
4 Correct 284 ms 85744 KB Output is correct
5 Correct 306 ms 86100 KB Output is correct
6 Correct 285 ms 86100 KB Output is correct
7 Correct 284 ms 86100 KB Output is correct
8 Correct 308 ms 87328 KB Output is correct
9 Correct 271 ms 87328 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 87328 KB Output is correct
2 Correct 275 ms 87328 KB Output is correct
3 Correct 666 ms 87328 KB Output is correct
4 Correct 930 ms 87664 KB Output is correct
5 Correct 1043 ms 89844 KB Output is correct
6 Correct 678 ms 89844 KB Output is correct
7 Correct 943 ms 89844 KB Output is correct
8 Correct 1018 ms 89888 KB Output is correct
9 Correct 1195 ms 95812 KB Output is correct
10 Correct 689 ms 95812 KB Output is correct
11 Correct 817 ms 95812 KB Output is correct
12 Correct 481 ms 95812 KB Output is correct
13 Correct 459 ms 95812 KB Output is correct
14 Correct 506 ms 95812 KB Output is correct
15 Correct 464 ms 95812 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 95812 KB Output is correct
2 Correct 249 ms 95812 KB Output is correct
3 Correct 558 ms 95812 KB Output is correct
4 Correct 902 ms 95812 KB Output is correct
5 Correct 1061 ms 95812 KB Output is correct
6 Correct 1224 ms 96180 KB Output is correct
7 Correct 721 ms 96180 KB Output is correct
8 Correct 930 ms 96180 KB Output is correct
9 Correct 506 ms 96180 KB Output is correct
10 Correct 470 ms 96180 KB Output is correct
11 Correct 413 ms 96180 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 921 ms 104344 KB Output is correct
2 Correct 1620 ms 117612 KB Output is correct
3 Correct 712 ms 117612 KB Output is correct
4 Correct 2383 ms 128008 KB Output is correct
5 Runtime error 980 ms 237336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -