oj.uz

Submission #367736

# Submission time Handle Problem Language Result Execution time Memory
367736 2021-02-18T07:45:24 Z arnold518 Zagrade (COI20_zagrade) C++14
0 / 100
 1 ms 384 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 = 10000;

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;
}

struct UF
{
	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);
		par[x]=y;
	}
}uf;

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

vector<vector<int>> vis;

int main()
{
	scanf("%d%d", &N, &M);
	A=vector<vector<int>>(N+10, vector<int>(M+10));
	vis=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++) uf.par[i]=i;
	for(int i=1; i<=N; i++)
	{
		for(int j=1; j<=M; j++)
		{
			if(i!=N && A[i][j]==A[i+1][j])
			{
				uf.Union(f(i, j), f(i+1, j));
			}
			if(j!=M && A[i][j]==A[i][j+1])
			{
				uf.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 nowy=B[i].y, nowx=B[i].x;
		if(A[nowy][nowx]==B[i].c) continue;
		queue<pii> QQ;
		QQ.push({nowy, nowx});
		int col=A[nowy][nowx];
		A[nowy][nowx]=B[i].c;
		while(!QQ.empty())
		{
			pii now=QQ.front(); QQ.pop();
			for(int t=0; t<4; t++)
			{
				int ny=now.first+dy[t], nx=now.second+dx[t];
				if(!(1<=ny && ny<=N && 1<=nx && nx<=M)) continue;
				if(A[ny][nx]==col)
				{
					A[ny][nx]=B[i].c;
					QQ.push({ny, nx});
				}
			}
		}
	}

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

Compilation message

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

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 364 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 384 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 364 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 364 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -