Submission #381350

#TimeUsernameProblemLanguageResultExecution timeMemory
381350AraragiPaint (COI20_paint)C++17
0 / 100
3092 ms5740 KiB
#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(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...