제출 #847316

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
847316		BidoTeima	Paint (COI20_paint)	C++17	0 / 100	354 ms	524288 KiB

paint

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
vector<vector<pair<int,int>>>par;
vector<vector<vector<pair<int,int>>>>adj;
vector<vector<int>>color;
pair<int, int> find_set(int a, int b){
    if(par[a][b] == make_pair(a, b))
        return make_pair(a, b);
    return par[a][b] = find_set(par[a][b].first, par[a][b].second);
}
bool merge(int a, int b, int x, int y){
    a = find_set(a, b).first, b = find_set(a,b).second;
    x = find_set(x, y).first, y = find_set(x, y).second;
    if(a == x && b == y){
        return 0;
    }
    if(color[a][b] != color[x][y])
        return 0;
    if(adj[a][b].size() == adj[x][y].size() ? rand() % 2 : adj[a][b].size() < adj[x][y].size())
        swap(a, x), swap(b, y);
    par[x][y] = make_pair(a, b);
    color[x][y] = color[a][b];
    for(pair<int,int>&pa:adj[a][b]){
        merge(a, b, pa.first, pa.second);
    }
    for(pair<int,int>& pa : adj[x][y]){
        if(!merge(a, b, pa.first, pa.second))
            adj[a][b].push_back(make_pair(pa.first, pa.second));
    }
    return 1;
}
int main()
{
    srand(time(0));
    cin>>n>>m;
    par=vector<vector<pair<int,int>>>(n+1, vector<pair<int,int>>(m+1));
    adj=vector<vector<vector<pair<int,int>>>>(n+1,vector<vector<pair<int,int>>>(m+1));
    color=vector<vector<int>>(n+1,vector<int>(m+1));
    int c[n+1][m+1];
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            par[i][j] = make_pair(i, j); 
            cin>>c[i][j];
            color[i][j] = c[i][j];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i >= 2){
                merge(i, j, i - 1, j);
            }
            if(j >= 2){
                merge(i, j, i, j - 1);
            }
            if(i + 1 <= n){
                merge(i, j, i + 1, j);
            }
            if(j + 1 <= m){
                merge(i, j, i, j + 1);
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i >= 2 && c[i][j] != c[i - 1][j]){
                pair<int,int>p1 = find_set(i, j);
                pair<int,int>p2 = find_set(i - 1, j);
                adj[p1.first][p1.second].push_back(make_pair(p2.first,p2.second));
                adj[p2.first][p2.second].push_back(make_pair(p1.first,p1.second));
            }
            if(j >= 2 && c[i][j] != c[i][j - 1]){
                pair<int,int>p1 = find_set(i, j);
                pair<int,int>p2 = find_set(i, j - 1);
                adj[p1.first][p1.second].push_back(make_pair(p2.first,p2.second));
                adj[p2.first][p2.second].push_back(make_pair(p1.first,p1.second));
            }
            if(i + 1 <= n && c[i][j] != c[i + 1][j]){
                pair<int,int>p1 = find_set(i, j);
                pair<int,int>p2 = find_set(i + 1, j);
                adj[p1.first][p1.second].push_back(make_pair(p2.first,p2.second));
                adj[p2.first][p2.second].push_back(make_pair(p1.first,p1.second));
            }
            if(j + 1 <= m && c[i][j] != c[i][j + 1]){
                pair<int,int>p1 = find_set(i, j);
                pair<int,int>p2 = find_set(i, j + 1);
                adj[p1.first][p1.second].push_back(make_pair(p2.first,p2.second));
                adj[p2.first][p2.second].push_back(make_pair(p1.first,p1.second));
            }

        }
    }
    int q;
    cin>>q;
    while(q--){
        int i,j,c;
        cin>>i>>j>>c; 
        pair<int,int>p = find_set(i, j);
        color[p.first][p.second] = c;
        if(i >= 2){
            merge(i, j, i - 1, j);
        }
        if(j >= 2){
            merge(i, j, i, j - 1);
        }
        if(i + 1 <= n){
            merge(i, j, i + 1, j);
        }
        if(j + 1 <= m){
            merge(i, j, i, j + 1);
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cout<<color[find_set(i, j).first][find_set(i, j).second]<<' ';
        }
        cout<<'\n';
    }
    return 0;
}

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