oj.uz

Submission #1003955

# Submission time Handle Problem Language Result Execution time Memory
1003955 2024-06-20T20:49:31 Z vjudge1 Paint (COI20_paint) C++17
31 / 100
 107 ms 46740 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
const int maxn = -1;
const int inf = 1e18+10;

vector<vector<int>> a, dscol;
vector<vector<pair<int,int>>> ds;
vector<vector<vector<pair<int,int>>>> dsedg;
vector<pair<int,int>> adj = {{0,1},{0,-1},{1,0},{-1,0}};

pair<int,int> find(pair<int,int> u) {
	if(u == ds[u.fr][u.sc]) return u;
	return ds[u.fr][u.sc] = find(ds[u.fr][u.sc]);
}

void join(pair<int,int> u, pair<int,int> v) {
	u = find(u);
	v = find(v);
	if(u == v) return;
	if(dsedg[u.fr][u.sc].size() < dsedg[v.fr][v.sc].size()) swap(u,v);
	ds[v.fr][v.sc] = u;
	for(auto x : dsedg[v.fr][v.sc]) {
		dsedg[u.fr][u.sc].pb(x);
	}
}

void upd(pair<int,int> u) {
	u = find(u);
	dscol[u.fr][u.sc]^= 1;
	vector<pair<int,int>> edgs = dsedg[u.fr][u.sc];
	dsedg[u.fr][u.sc].clear();
	for(auto v : edgs) {
		join(u,v);
	}
}

int32_t main() {
	// #ifndef ONLINE_JUDGE
	//freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
	// #endif

	int n,m;
	cin >> n >> m;

	ds.resize(n+1,vector<pair<int,int>>(m+1));
	a.resize(n+1,vector<int>(m+1));
	dscol.resize(n+1,vector<int>(m+1));
	dsedg.resize(n+1,vector<vector<pair<int,int>>>(m+1));
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> a[i][j];
			dscol[i][j] = a[i][j];
			ds[i][j] = mp(i,j);
		}
	}

	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			for(auto X : adj) {
				int i1 = i+X.fr;
				int j1 = j+X.sc;
				if(i1 >= 1 && i1 <= n && j1 >= 1 && j1 <= m) {
					if(a[i][j] != a[i1][j1]) dsedg[i][j].pb(mp(i1,j1));
				}
			}
		}
	}

	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			for(auto X : adj) {
				int i1 = i+X.fr;
				int j1 = j+X.sc;
				if(i1 >= 1 && i1 <= n && j1 >= 1 && j1 <= m) {
					if(a[i][j] == a[i1][j1]) join(mp(i,j),mp(i1,j1));
				}
			}
		}
	}

	int q;cin >> q;
	while(q--) {
		int i,j,c;
		cin >> i >> j >> c;
		pair<int,int> u = mp(i,j);
		u = find(u);

		if(c == dscol[u.fr][u.sc]) continue;
		upd(u);
	}

	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			pair<int,int> u = mp(i,j);
			u = find(u);
			cout << dscol[u.fr][u.sc] << " ";
		}
		cout << endl;
	}

}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 9588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 43540 KB Output is correct
2 Correct 87 ms 40372 KB Output is correct
3 Correct 107 ms 44848 KB Output is correct
4 Correct 104 ms 46740 KB Output is correct
5 Correct 99 ms 41092 KB Output is correct

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 33760 KB Output isn't correct
2 Halted 0 ms 0 KB -