Submission #1126740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126740		Zero_OP	Paint (COI20_paint)	C++17	8 / 100	3094 ms	5172 KiB

paint

#include <bits/stdc++.h>

using namespace std;

int R, C, n;
vector<vector<int>> cl, id;
vector<vector<bool>> vis;

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

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

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    cin >> R >> C;

    cl.resize(R, vector<int>(C));
    id.resize(R, vector<int>(C));
    n = 0;

    for(int i = 0; i < R; ++i){
        for(int j = 0; j < C; ++j){
            cin >> cl[i][j];
            id[i][j] = n++;
        }
    }

    vis.resize(R, vector<bool>(C, false));

    int Q; cin >> Q;

    while(Q--){
        int r, c, new_cl;
        cin >> r >> c >> new_cl;
        --r, --c;

        int old = cl[r][c];

        vector<pair<int, int>> changed;
        queue<pair<int, int>> q;
        q.push({r, c});
        vis[r][c] = true;

        while(!q.empty()){
            int r, c; tie(r, c) = q.front(); q.pop();
            changed.emplace_back(r, c);
            for(int i = 0; i < 4; ++i){
                int nr = r + dx[i], nc = c + dy[i];
                if(0 <= nr && nr < R && 0 <= nc && nc < C && !vis[nr][nc] && cl[nr][nc] == old){
                    vis[nr][nc] = true;
                    q.push({nr, nc});
                }
            }
        }

        for(auto [r, c] : changed){
            cl[r][c] = new_cl;
            vis[r][c] = false;
        }
    }

    for(int i = 0; i < R; ++i){
        for(int j = 0; j < C; ++j){
            cout << cl[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 31
• Subtask 4: 0 / 52