Submission #1003955

#TimeUsernameProblemLanguageResultExecution timeMemory
1003955vjudge1Paint (COI20_paint)C++17
31 / 100
107 ms46740 KiB
#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; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...