oj.uz

답안 #381455

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
381455 2021-03-25T08:04:50 Z topovik Paint (COI20_paint) C++14
8 / 100
 3000 ms 17752 KB 
#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]));
}

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()
{
    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;
    }
}

Compilation message

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.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 6 ms 5248 KB Output is correct
3 Correct 14 ms 5484 KB Output is correct
4 Correct 15 ms 5484 KB Output is correct
5 Correct 251 ms 5760 KB Output is correct
6 Correct 224 ms 5612 KB Output is correct
7 Correct 4 ms 4972 KB Output is correct

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 7412 KB Output is correct
2 Correct 137 ms 9708 KB Output is correct
3 Execution timed out 3053 ms 11292 KB Time limit exceeded

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1647 ms 16928 KB Output is correct
2 Correct 364 ms 16636 KB Output is correct
3 Correct 395 ms 17392 KB Output is correct
4 Correct 1509 ms 17752 KB Output is correct
5 Execution timed out 3054 ms 16380 KB Time limit exceeded

Subtask #4
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 204 ms 14332 KB Output is correct
2 Execution timed out 3069 ms 17324 KB Time limit exceeded
3 Halted 0 ms 0 KB -