제출 #381461

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
381461		topovik	Paint (COI20_paint)	C++14	8 / 100	3071 ms	17028 KiB

paint

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define len(x) x.size()
#define debug(x) cout << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef long double ld;

const ll N = 2e5 + 100;
const ll oo = 1e9 + 7;

vector <int> edges[N];
int color[N];
int pred[N];
int n, m;

int get(int x)
{
    if (x == pred[x]) return x;
    else return (pred[x] = get(pred[x]));
}

inline int pos(int x, int y)
{
    return x * m + y;
}

void unite(int x, int y)
{
    x = get(x);
    y = get(y);
    if (x == y) return;
    if (color[x] != color[y]) return;
    if (edges[x].size() < edges[y].size()) swap(x, y);
    pred[y] = x;
    for (int i = 0; i < edges[y].size(); i++)
        if (get(edges[y][i]) != x) edges[x].pb(edges[y][i]);
}

int main()
{
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    vector <vector <int> > a;
    a.resize(n);
    for (int i = 0; i < n; i++) a[i].resize(m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) cin >> a[i][j];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) color[pos(i, j)] = a[i][j], pred[pos(i, j)] = pos(i, j);
    for (int i = 0; i < n; i++)
    {
        if (i < n - 1)
        {
            for (int j = 0; j < m; j++)
              if (a[i][j] != a[i + 1][j])
            {
                edges[pos(i, j)].pb(pos(i + 1, j));
                edges[pos(i + 1, j)].pb(pos(i, j));
            }
        }
        for (int j = 0; j < m - 1; j++)
            if (a[i][j] != a[i][j + 1])
        {
            edges[pos(i, j)].pb(pos(i, j + 1));
            edges[pos(i, j + 1)].pb(pos(i, j));
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (i < n - 1)
        {
            for (int j = 0; j < m; j++)
                if (a[i][j] == a[i + 1][j]) unite(pos(i, j), pos(i + 1, j));
        }
        for (int j = 0; j < m - 1; j++)
            if (a[i][j] == a[i][j + 1]) unite(pos(i, j), pos(i, j + 1));
    }
    int q;
    cin >> q;
    while (q--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        x--, y--;
        int ps = get(pos(x, y));
        if (color[ps] != z)
        {
            color[ps] = z;
            int sz = edges[ps].size();
            for (int i = 0; i < sz; i++) unite(ps, edges[ps][i]);
        }
    }
    cout << endl;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++) cout << color[get(pos(i, j))] << " ";
        cout << endl;
    }
}

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

paint.cpp: In function 'void unite(int, int)':
paint.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 0; i < edges[y].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~

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