oj.uz

Submission #381350

# Submission time Handle Problem Language Result Execution time Memory
381350 2021-03-25T06:48:56 Z Araragi Paint (COI20_paint) C++17
0 / 100
 3000 ms 5740 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("00")
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
const int inf = 1e9;
const ll inf64 = 1e18;
#define ft first
#define fin(x) ifstream cin("x.in");
#define fout(x) ofstream cout("x.out");
#define sd second
#define pb push_back
#define sz(x) (int)x.size()

int who[10001][10001];
int x, y;
bool bad[10001][10001];
int grid[10001][10001];
int where[500001];
int n, m;
queue< pair<int, int> > q;

int d[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

bool valid(int x, int y) {return (x >= 0 && x < n && y >= 0 && y < m && !bad[x][y]);}


void bfs(bool needUpdate, bool needDebug)
{
    if (needUpdate)
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                grid[i][j] = where[who[i][j]];
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            bad[i][j] = false;

   // if (needDebug)
   // {
   //     for (int i = 0; i < n; i++, cout << '\n')
   //         for (int j = 0; j < m; j++)
   //             cerr << grid[i][j] << " ";
   //     cout << '\n';
   // }


    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            who[i][j] = -1;

    int now = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (!bad[i][j])
            {
                q.push({i, j});
                now++;
                bad[i][j] = true;

                while (!q.empty())
                {
                    auto z = q.front(); q.pop();
                    x = z.ft;
                    y = z.sd;

                    if (who[x][y] == -1)
                        who[x][y] = now;

                    for (int i = 0; i < 4; i++)
                    {
                        int cx = x + d[i][0];
                        int cy = y + d[i][1];

                        if (valid(cx, cy) && grid[x][y] == grid[cx][cy])
                        {
                            q.push({cx, cy});
                            bad[cx][cy] = true;
                        }
                    }
                }
            }

    if (needDebug)
    {
        for (int i = 0; i < n; i++, cout << '\n')
            for (int j = 0; j < m; j++)
                cerr << who[i][j] << " ";

        cout << '\n';
    }

    for (int i = 1; i <= now; i++)
        where[i] = -1;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (where[who[i][j]] == -1)
                where[who[i][j]] = grid[i][j];
}

void solve()
{
    cin >> n >> m;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    bfs(0, 0);

    int q;
    cin >> q;

    while (q--)
    {
        int x, y, to;
        cin >> x >> y >> to;
        --x; --y;
        where[who[x][y]] = to;
        bfs(1, 0);
    }

    for (int i = 0; i < n; i++, cout << '\n')
        for (int j = 0; j < m; j++)
            cout << where[who[i][j]] << " ";
}

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

    #ifdef _LOCAL_
        system("color 2");
    #endif // _LOCAL_

    int t = 1;

    while (t--)
        solve();

}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 620 KB Output is correct
2 Correct 20 ms 876 KB Output is correct
3 Execution timed out 3075 ms 748 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3092 ms 1004 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3058 ms 4076 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3088 ms 5740 KB Time limit exceeded
2 Halted 0 ms 0 KB -