oj.uz

Submission #367764

# Submission time Handle Problem Language Result Execution time Memory
367764 2021-02-18T09:33:56 Z arnold518 Paint (COI20_paint) C++14
48 / 100
 3000 ms 50144 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 200000;

const int dy[] = {-1, 1, 0, 0};
const int dx[] = {0, 0, -1, 1};

int N, M, Q;
vector<vector<int>> A;

int f(int y, int x)
{
	return x+(y-1)*M;
}

int C[MAXN+10];

struct Data
{
	int y, x, c;
};
Data B[MAXN+10];

unordered_set<int> adj[MAXN+10];
int par[MAXN+10];
int Find(int x)
{
	if(x==par[x]) return x;
	return par[x]=Find(par[x]);
}
void Union(int x, int y)
{
	x=Find(x); y=Find(y);
	if(adj[x].size()>adj[y].size()) swap(x, y);
	for(auto it : adj[x])
	{
		int t=Find(it);
		if(t==y) continue;
		if(t==x) continue;
		adj[y].insert(t);
		adj[t].erase(x);
		adj[t].insert(y);
	}
	adj[y].erase(x);
	par[x]=y;
}

int main()
{
	scanf("%d%d", &N, &M);
	A=vector<vector<int>>(N+10, vector<int>(M+10));

	for(int i=1; i<=N; i++)
	{
		for(int j=1; j<=M; j++)
		{
			scanf("%d", &A[i][j]);
		}
	}

	for(int i=1; i<=N*M; i++) par[i]=i;
	for(int i=1; i<=N; i++)
	{
		for(int j=1; j<=M; j++)
		{
			if(i!=N)
			{
				if(A[i][j]!=A[i+1][j])
				{
					adj[f(i, j)].insert(f(i+1, j));
					adj[f(i+1, j)].insert(f(i, j));
				}
			}
			if(j!=M)
			{
				if(A[i][j]!=A[i][j+1])
				{
					adj[f(i, j+1)].insert(f(i, j));
					adj[f(i, j)].insert(f(i, j+1));					
				}
			}
		}
	}
	for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) C[f(i, j)]=A[i][j];

	for(int i=1; i<=N; i++)
	{
		for(int j=1; j<=M; j++)
		{
			if(i!=N)
			{
				if(A[i][j]==A[i+1][j])
				{
					Union(f(i, j), f(i+1, j));
				}
			}
			if(j!=M)
			{
				if(A[i][j]==A[i][j+1])
				{
					Union(f(i, j), f(i, j+1));
				}
			}
		}
	}

	scanf("%d", &Q);
	for(int i=1; i<=Q; i++)
	{
		scanf("%d%d%d", &B[i].y, &B[i].x, &B[i].c);
	}

	for(int i=1; i<=Q; i++)
	{
		int now=Find(f(B[i].y, B[i].x));
		if(C[now]==B[i].c) continue;
		C[now]=B[i].c;

		vector<int> VV;
		for(auto nxt : adj[now])
		{
			nxt=Find(nxt);
			if(C[nxt]==C[now])
			{
				VV.push_back(nxt);
			}
		}
		for(auto it : VV) Union(it, now);
	}

	for(int i=1; i<=N; i++)
	{
		for(int j=1; j<=M; j++)
		{
			printf("%d ", C[Find(f(i, j))]);
		}
		printf("\n");
	}
}

Compilation message

paint.cpp: In function 'int main()':
paint.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
paint.cpp:62:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |    scanf("%d", &A[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~
paint.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  112 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
paint.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  115 |   scanf("%d%d%d", &B[i].y, &B[i].x, &B[i].c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11532 KB Output is correct
2 Correct 10 ms 11500 KB Output is correct
3 Correct 18 ms 13164 KB Output is correct
4 Correct 22 ms 13036 KB Output is correct
5 Correct 50 ms 12908 KB Output is correct
6 Correct 44 ms 12908 KB Output is correct
7 Correct 10 ms 11244 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 20196 KB Output is correct
2 Correct 156 ms 26404 KB Output is correct
3 Correct 141 ms 34268 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 49260 KB Output is correct
2 Correct 339 ms 50144 KB Output is correct
3 Correct 350 ms 49644 KB Output is correct
4 Correct 413 ms 49900 KB Output is correct
5 Correct 344 ms 47852 KB Output is correct

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 41836 KB Output is correct
2 Execution timed out 3076 ms 44200 KB Time limit exceeded
3 Halted 0 ms 0 KB -