제출 #837200

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
837200		Liudas	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	2 ms	212 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
bool connects(int Y, int X, vector<vector<int>> copy, int H, int W){
    queue<pair<int, int>> que;
    que.push({X, Y});
    while(!que.empty()){
        int x = que.front().first, y = que.front().second;
        que.pop();
        if(!copy[x][y]){
            continue;
        }
        copy[x][y] = 0;
        if(x > 0){
            que.push({x-1, y});
        }
        if(y > 0){
            que.push({x, y-1});
        }
        if(x < H-1){
            que.push({x+1, y});
        }
        if(y < W-1){
            que.push({x, y+1});
        }
    }
    int ok = 0;
    for(auto i :copy){
        for(int j : i){
            ok |= j;
        }
    }
    //cout << "AFTER CHECK" << endl;
   // for(int i = 0; i < H; i ++){
       // for(int j = 0; j < W; j ++){
          //  cout << copy[i][j] << " ";
       // }
        //cout << endl;
    //}
    //cout << endl << endl;
    if(!ok){
        return true;
    }
    return false;
}
int main(){
    int H, W;
    cin >> H >> W;
    set<vector<int>> in, out;
    vector<vector<int>> grid(H, vector<int>(W));
    int minx, miny, mini = 1e9, maxx, maxy, maxi = 0;
    for(int i = 0; i < H; i ++){
        for(int j = 0; j < W; j ++){
            cin >> grid[i][j];
            if(maxi < grid[i][j]){
                maxi = grid[i][j];
                maxy = j;
                maxx = i;
            }
            if(mini > grid[i][j]){
                mini = grid[i][j];
                miny = j;
                minx = i;
            }
        }
    }
    int L = 0, R = 1000000000;
    while(L < R){
        int mid = (L + R) / 2;
        vector<vector<int>> copy = grid;
        int max_can = mini + mid, max_got = 0, min_left = 1e9;
        queue<pair<int, int>> que;
        que.push({minx, miny});
        while(!que.empty()){
            int x = que.front().first, y = que.front().second;
            que.pop();
            if(grid[x][y] > max_can || (x==maxx && y == maxy) || !copy[x][y]){
                continue;
            }
            copy[x][y] = 0;
            bool can = connects(maxy, maxx, copy, H, W);
            //cout << can << endl;
            if(!can){
                copy[x][y] = grid[x][y];
                continue;
            }
            else{
                if(x > 0){
                    que.push({x-1, y});
                }
                if(y > 0){
                    que.push({x, y-1});
                }
                if(x < H-1){
                    que.push({x+1, y});
                }
                if(y < W-1){
                    que.push({x, y+1});
                }
            }
        }
        int min_untaken = 1e9;
        for(int i = 0; i < H; i ++){
            for(int j = 0; j < W; j ++){
                //cout << copy[i][j] << " ";
                if(copy[i][j])
                min_untaken = min(min_untaken, grid[i][j]);
            }
            //cout << endl;
        }
        int delta = max(mid, maxi - min_untaken);
        //cout << mid << " " << delta << endl;
        if(delta > mid){
            L = mid + 1;
        }
        else{
            R = mid;
        }
    }
    cout << L << endl;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

joioi.cpp: In function 'int main()':
joioi.cpp:70:35: warning: unused variable 'max_got' [-Wunused-variable]
   70 |         int max_can = mini + mid, max_got = 0, min_left = 1e9;
      |                                   ^~~~~~~
joioi.cpp:70:48: warning: unused variable 'min_left' [-Wunused-variable]
   70 |         int max_can = mini + mid, max_got = 0, min_left = 1e9;
      |                                                ^~~~~~~~
joioi.cpp:76:49: warning: 'maxy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |             if(grid[x][y] > max_can || (x==maxx && y == maxy) || !copy[x][y]){
      |                                        ~~~~~~~~~^~~~~~~~~~~~~
joioi.cpp:76:37: warning: 'maxx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |             if(grid[x][y] > max_can || (x==maxx && y == maxy) || !copy[x][y]){

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40