oj.uz

Submission #381461

# Submission time Handle Problem Language Result Execution time Memory
381461 2021-03-25T08:08:24 Z topovik Paint (COI20_paint) C++14
8 / 100
 3000 ms 17028 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]));
}

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;
    }
}

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 5 ms 5100 KB Output is correct
3 Correct 9 ms 5484 KB Output is correct
4 Correct 10 ms 5612 KB Output is correct
5 Correct 242 ms 5740 KB Output is correct
6 Correct 220 ms 5740 KB Output is correct
7 Correct 4 ms 5100 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 7404 KB Output is correct
2 Correct 81 ms 9708 KB Output is correct
3 Execution timed out 3063 ms 11416 KB Time limit exceeded

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1623 ms 16608 KB Output is correct
2 Correct 331 ms 16136 KB Output is correct
3 Correct 354 ms 16604 KB Output is correct
4 Correct 1459 ms 17028 KB Output is correct
5 Execution timed out 3071 ms 15484 KB Time limit exceeded

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 14120 KB Output is correct
2 Execution timed out 3071 ms 15772 KB Time limit exceeded
3 Halted 0 ms 0 KB -