| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 857747 |
2023-10-06T19:32:53 Z |
Denjell |
Paint (COI20_paint) |
C++14 |
|
3000 ms |
62208 KB |
#include <bits/stdc++.h>
#include <random>
#include <ctime>
using namespace std;
typedef int64_t ll;
template<typename T> istream& operator>>(istream& is, vector<T>& v) { for (auto& i : v) is >> i; return is; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) { for (auto& i : v) os << i << "\n"; return os; }
template<typename T> istream& operator>>(istream& is, pair<T, T>& v) { is >> v.first >> v.second; return is; }
template<typename T> ostream& operator<<(ostream& os, const pair<T, T>& v) { os << v.first << " " << v.second; return os; }
#define MOD 1000000007
//#define MOD 998244353
uint64_t gcd(uint64_t a, uint64_t b) {
uint64_t r;
while (b != 0) {
r = a % b;
a = b;
b = r;
}
return a;
}
uint64_t mypow(uint64_t base, uint64_t exp) {
uint64_t result = 1;
while (exp > 0) {
if (exp & 1) result = (result * base);
base = (base * base);
exp >>= 1;
}
return result;
}
uint64_t modpow(uint64_t base, uint64_t exp, uint64_t modulus) {
base %= modulus;
uint64_t result = 1;
while (exp > 0) {
if (exp & 1) result = (result * base) % modulus;
base = (base * base) % modulus;
exp >>= 1;
}
return result;
}
inline int log2(uint64_t n) {
unsigned int r = 0;
while (n >>= 1) r++;
return r;
}
int64_t egcd(int64_t a, int64_t b, int64_t& x, int64_t& y) {
x = 1, y = 0;
int x1 = 0, y1 = 1, a1 = a, b1 = b;
while (b1) {
int q = a1 / b1;
tie(x, x1) = make_tuple(x1, x - q * x1);
tie(y, y1) = make_tuple(y1, y - q * y1);
tie(a1, b1) = make_tuple(b1, a1 - q * b1);
}
return a1;
}
inline uint64_t modinv(uint64_t x, uint64_t mod) {
return modpow(x, mod - 2, mod);
}
void precomp() {
}
struct DSU {
DSU(int parent = -1) : parent(parent), color(-1) {}
int parent;
int color;
set<int> neighbours;
};
void init(vector<DSU>& a) {
for (int i = 0; i < a.size(); i++) a[i].parent = i;
}
int find_set(vector<DSU>& a, int v) {
if (v == a[v].parent) return v;
return a[v].parent = find_set(a, a[v].parent);
}
void union_sets(vector<DSU>& a, int u, int v) {
u = find_set(a, u);
v = find_set(a, v);
if (u != v) {
if (a[u].neighbours.size() < a[v].neighbours.size()) swap(u, v);
a[v].parent = u;
for (auto n : a[v].neighbours) {
if (u != find_set(a, n)) {
a[u].neighbours.insert(n);
}
}
}
}
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };
void solve() {
ll n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
cin >> a;
auto p = [m](int r, int c) {
return r * m + c;
};
auto valid = [n, m](int r, int c) {
return r >= 0 && r < n && c >= 0 && c < m;
};
vector<DSU> b(n * m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
b[p(i, j)].color = a[i][j];
b[p(i, j)].parent = p(i,j);
for (int k = 0; k < 4; k++) {
auto nx = i + dx[k];
auto ny = j + dy[k];
if (!valid(nx, ny)) continue;
b[p(i, j)].neighbours.insert(p(nx, ny));
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < 2; k++) { // 2 since only look right and down
auto nx = i + dx[k];
auto ny = j + dy[k];
if (!valid(nx, ny)) continue;
auto pold = find_set(b, p(i, j));
auto pnew = find_set(b, p(nx, ny));
if (b[pold].color == b[pnew].color) {
union_sets(b, pold, pnew);
}
}
}
}
ll q;
cin >> q;
for (int i = 0; i < q; i++) {
ll x, y, c;
cin >> x >> y >> c;
x--; y--;
auto pos = find_set(b, p(x, y));
b[pos].color = c;
vector<int> tomerge;
for (auto it = b[pos].neighbours.begin(); it != b[pos].neighbours.end();) {
auto pnew = find_set(b, *it);
if (pos == pnew) {
it = b[pos].neighbours.erase(it);
}
else {
if (b[pos].color == b[pnew].color) {
tomerge.push_back(pnew);
}
it++;
}
}
for (auto e : tomerge) {
auto pos = find_set(b, p(x, y));
union_sets(b, e, pos);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
auto pos = find_set(b, p(i, j));
cout << b[pos].color << " ";
}
cout << "\n";
}
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
precomp();
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
Compilation message
paint.cpp: In function 'void init(std::vector<DSU>&)':
paint.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<DSU>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int i = 0; i < a.size(); i++) a[i].parent = i;
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
860 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2652 KB |
Output is correct |
| 4 |
Correct |
7 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
68 ms |
3452 KB |
Output is correct |
| 6 |
Correct |
9 ms |
3672 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
8344 KB |
Output is correct |
| 2 |
Correct |
62 ms |
17356 KB |
Output is correct |
| 3 |
Correct |
102 ms |
35980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
151 ms |
53072 KB |
Output is correct |
| 2 |
Correct |
148 ms |
53888 KB |
Output is correct |
| 3 |
Correct |
160 ms |
53072 KB |
Output is correct |
| 4 |
Correct |
183 ms |
52160 KB |
Output is correct |
| 5 |
Correct |
142 ms |
47496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
152 ms |
43348 KB |
Output is correct |
| 2 |
Execution timed out |
3054 ms |
62208 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
