oj.uz

Submission #381501

# Submission time Handle Problem Language Result Execution time Memory
381501 2021-03-25T08:40:20 Z Vimmer Paint (COI20_paint) C++14
48 / 100
 3000 ms 19564 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("-O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-Ofast")

#define N 200500
#define NN 1005000
#define PB push_back
#define endl '\n'
#define pri(x) cout << x << endl
#define _ << " " <<
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define M ll(1e9 + 7)
#define F first
#define S second

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef short int si;
typedef unsigned long long ull;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

//ordered_set se;

int n, m;

vector <int> who[N];

int mk[N];

int pr[N], clr[N], qr;

int fnd(int x) {if (pr[x] != x) pr[x] = fnd(pr[x]); return pr[x];}
int ind(int i, int j) {return i * m + j;}

void link(int x, int y)
{
    x = fnd(x); y = fnd(y);

    if (x == y) return;

    if (sz(who[y]) > sz(who[x]))
        swap(x, y);

    for (auto it : who[y])
        who[x].PB(it);

    pr[y] = x;
}

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

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

//    freopen("1.in", "r", stdin);
//
//    freopen("1.out", "w", stdout);

    cin >> n >> m;

    int a[n][m];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            {cin >> a[i][j]; int id = ind(i, j); clr[id] = a[i][j]; pr[id] = id;}

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            if (i != 0 && a[i - 1][j] == a[i][j])
                link(ind(i - 1, j), ind(i, j));

            if (j != 0 && a[i][j - 1] == a[i][j])
                link(ind(i, j - 1), ind(i, j));
        }

    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
      {
          int idr = fnd(ind(i, j));

          for (int u = 0; u < 4; u++)
          {
              int cx = i + b[u][0];

              int cy = j + b[u][1];

              if (0 <= cx && cx < n && 0 <= cy && cy < m && a[cx][cy] != a[i][j])
                  who[idr].PB(fnd(ind(cx, cy)));
          }
      }

    int q;

    cin >> q;

    for (; q > 0; q--)
    {
        qr++;

        int x, y, c;

        cin >> x >> y >> c;

        x--; y--;

        int id = fnd(ind(x, y));

        if (clr[id] == c) continue;

        clr[id] = c;

        vector <int> nx; nx.clear();

        vector <int> lnk; lnk.clear();

        for (auto it : who[id])
        {
            it = fnd(it);

            if (mk[it] == qr) continue;

            mk[it] = qr;

            if (clr[it] == c)
                lnk.PB(it);
                    else nx.PB(it);
        }

        who[id] = nx;

//        cout << "LINKED: ";

        for (auto it : lnk)
            {
//                cout << fnd(it) << " ";

                link(fnd(id), fnd(it));
            }

//        cout << endl;
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cout << clr[fnd(ind(i, j))] << " ";

        cout << endl;
    }
}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 7404 KB Output is correct
2 Correct 82 ms 9300 KB Output is correct
3 Correct 113 ms 12268 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 19248 KB Output is correct
2 Correct 110 ms 18448 KB Output is correct
3 Correct 110 ms 19564 KB Output is correct
4 Correct 142 ms 19436 KB Output is correct
5 Correct 126 ms 17644 KB Output is correct

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 12652 KB Output is correct
2 Execution timed out 3078 ms 14220 KB Time limit exceeded
3 Halted 0 ms 0 KB -