제출 #1128378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1128378		Zero_OP	무지개나라 (APIO17_rainbow)	C++20	11 / 100	3095 ms	1114112 KiB

rainbow

#include "bits/stdc++.h"
#ifndef LOCAL
    #include "rainbow.h"
#endif

using namespace std;

const int MAX = 1e5 + 5;
const int dx[4] = {-1, +1, 0, 0};
const int dy[4] = {0, 0, +1, -1};

int R, C;
vector<vector<bool>> is_river, vis;

void init(int _R, int _C, int x, int y, int M, char *S) {
    R = _R;
    C = _C;
    is_river.resize(R + 1, vector<bool>(C + 1, false));
    vis.resize(R + 1, vector<bool>(C + 1, false));
    for(int i = 0; i <= M; ++i){
        assert(1 <= x && x <= R && 1 <= y && y <= C);
        is_river[x][y] = true;
        if(i < M){
            if(S[i] == 'N') --x;
            if(S[i] == 'S') ++x;
            if(S[i] == 'W') --y;
            if(S[i] == 'E') ++y;
        }
    }
}

int colour(int ar, int ac, int br, int bc) {
    for(int i = ar; i <= br; ++i){
        for(int j = ac; j <= bc; ++j){
            vis[i][j] = false;
        }
    }

    int cc = 0;
    queue<pair<int, int>> q;
    for(int i = ar; i <= br; ++i){
        for(int j = ac; j <= bc; ++j){
            if(!vis[i][j] && !is_river[i][j]){
                ++cc;
                q.push({i, j});
                vis[i][j] = true;
                while(!q.empty()){
                    int x, y;
                    tie(x, y) = q.front(); q.pop();
                    for(int i = 0; i < 4; ++i){
                        int nx = x + dx[i], ny = y + dy[i];
                        if(ar <= nx && nx <= br && ac <= ny && ny <= bc && !vis[nx][ny] && !is_river[nx][ny]){
                            vis[nx][ny] = true;
                            q.push({nx, ny});
                        }
                    }
                }
            }
        }
    }

    return cc;
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);

    int R, C, M, Q, sr, sc;
    cin >> R >> C >> M >> Q >> sr >> sc;

    char S[M];
    for(int i = 0; i < M; ++i) cin >> S[i];

    init(R, C, sr, sc, M, S);

    while(Q--){
        int ar, ac, br, bc;
        cin >> ar >> ac >> br >> bc;
        cout << colour(ar, ac, br, bc) << '\n';
    }


    return 0;
}
#endif // LOCAL

• Subtask 1: 11 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26