| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 381589 |
2021-03-25T10:33:38 Z |
kartel |
Paint (COI20_paint) |
C++14 |
|
1054 ms |
74220 KB |
#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <time.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define M ll(1e9 + 7)
//#define M ll(998244353)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
#define eps (ld)1e-9
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef double ld;
typedef unsigned long long ull;
typedef short int si;
const int N = 2e5 + 500;
int steps[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int n, m, qq;
vector < vector <int> > a, mk;
int l[N], pr[N], r[N], siz[N], color[N], ans[N];
set <int> ng[N];
int id(int x, int y) {return (x * m + y);}
int f(int x) {return (x == pr[x] ? x : pr[x] = f(pr[x]));}
void link(int x, int y, int c) {
x = f(x);
y = f(y);
if (x == y) {
return;
}
if (n == 1) {
if (siz[x] > siz[y]) {
swap(x, y);
}
l[y] = min(l[y], l[x]);
r[y] = max(r[y], r[x]);
color[y] = c;
pr[x] = y;
siz[y] += siz[x];
}
else {
if (sz(ng[x]) > sz(ng[y])) {
swap(x, y);
}
pr[x] = y;
siz[y] += siz[x];
color[y] = c;
for (auto p : ng[x]) {
ng[y].insert(p);
}
}
}
void solve() {
queue <pii> q;
while (qq--) {
int i, j, c;
cin >> i >> j >> c; i--; j--;
q.push({i, j});
int old = a[i][j];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
mk[i][j] = 0;
}
}
while (sz(q)) {
int x = q.front().F;
int y = q.front().S; q.pop();
a[x][y] = c;
for (int i = 0; i < 4; i++) {
int cx = x + steps[i][0];
int cy = y + steps[i][1];
if (cx < 0 || cy < 0 || cx >= n || cy >= m || a[cx][cy] != old || mk[cx][cy]) {
continue;
}
mk[cx][cy] = 1;
q.push({cx, cy});
}
}
}
for (int i = 0; i < n; i++, cout << el) {
for (int j = 0; j < m; j++) {
cout << a[i][j] << " ";
}
}
exit(0);
}
void upd(int x, int nc) {
x = f(x);
color[x] = nc;
if (l[x] && color[f(l[x] - 1)] == color[x]) {
link(l[x] - 1, x, nc);
}
if (r[x] < m - 1 && color[f(r[x] + 1)] == color[x]) {
link(r[x] + 1, x, nc);
}
}
void solve1() {
for (int j = 0; j < m; j++) {
if (j && a[0][j - 1] == a[0][j]) {
link(j - 1, j, 0);
}
if (j < m - 1 && a[0][j] == a[0][j + 1]) {
link(j, j + 1, 0);
}
}
for (int j = 0; j < m; j++) {
color[f(j)] = a[0][j];
}
while (qq--) {
int x, y, c;
cin >> x >> y >> c; x--; y--;
if (n == 1) {
upd(y, c);
}
}
for (int j = 0; j < m; j++) {
if (mk[0][j]) {
cout << ans[j] << " ";
continue;
}
int x = f(j);
int c = color[x];
for (int i = l[x]; i <= r[x]; i++) {
ans[i] = c;
mk[0][i] = 1;
}
cout << ans[j] << " ";
}
cout << el;
}
void solve2() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int d = id(i, j);
pr[d] = d;
siz[d] = 1;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < 4; k++) {
int x = i + steps[k][0];
int y = j + steps[k][1];
if (x < 0 || y < 0 || x >= n || y >= m || a[x][y] != a[i][j]) {
continue;
}
link(id(i, j), id(x, y), 0);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// cerr << f(id(i, j)) << " ";
for (int k = 0; k < 4; k++) {
int x = i + steps[k][0];
int y = j + steps[k][1];
if (x < 0 || y < 0 || x >= n || y >= m || a[x][y] == a[i][j]) {
continue;
}
int par = f(id(i, j));
ng[par].insert(f(id(x, y)));
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
color[f(id(i, j))] = a[i][j];
}
}
while (qq--) {
int i, j, c;
cin >> i >> j >> c;
i--; j--;
assert(c <= 1);
int ID = id(i, j);
int par = f(ID);
if (color[par] == c) {
continue;
}
color[par] = c;
set <int> negs = ng[par];
ng[par].clear();
for (auto x : negs) {
link(ID, x, c);
}
}
for (int i = 0; i < n; i++, cout << el) {
for (int j = 0; j < m; j++) {
cout << color[f(id(i, j))] << " ";
}
}
cout << el;
}
int main()
{
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// in("toys.in");
// out("toys.out");
// in("input.txt");
// out("output.txt");
// cerr.precision(9); cerr << fixed;
// clock_t tStart = clock();
cin >> n >> m;
a.resize(n);
mk.resize(n);
for (int i = 0; i < n; i++) {
a[i].resize(m);
mk[i].resize(m);
for (int j = 0; j < m; j++) {
cin >> a[i][j];
pr[j] = j;
siz[j] = 1;
l[j] = j;
r[j] = j;
}
}
cin >> qq;
if (n * m * 1ll * qq <= (ll)100000000) {
solve();
}
else if (n == 1) {
solve1();
}
else {
solve2();
}
}
/*
7
4 6 7 2 3 1 5
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
9836 KB |
Output is correct |
| 2 |
Correct |
8 ms |
9836 KB |
Output is correct |
| 3 |
Correct |
65 ms |
9964 KB |
Output is correct |
| 4 |
Correct |
77 ms |
9836 KB |
Output is correct |
| 5 |
Correct |
603 ms |
9964 KB |
Output is correct |
| 6 |
Correct |
1054 ms |
9964 KB |
Output is correct |
| 7 |
Correct |
9 ms |
9836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
11472 KB |
Output is correct |
| 2 |
Correct |
53 ms |
13092 KB |
Output is correct |
| 3 |
Correct |
75 ms |
16760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
239 ms |
51436 KB |
Output is correct |
| 2 |
Correct |
223 ms |
51564 KB |
Output is correct |
| 3 |
Correct |
250 ms |
51180 KB |
Output is correct |
| 4 |
Correct |
285 ms |
49132 KB |
Output is correct |
| 5 |
Correct |
203 ms |
46060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
110 ms |
74220 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
