Submission #736141

#	Time	Username	Problem	Language	Result	Execution time	Memory
736141		marvinthang	Zoo (COCI19_zoo)	C++17	110 / 110	156 ms	39092 KiB

zoo

/*************************************
*    author: marvinthang             *
*    created: 05.08.2022 11:16:36`    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                 div  ___div
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define             FULL(i)  (MASK(i) - 1)
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }

template <class T>             scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class T>            print_op(vector <T>)  { out << '{'; for (size_t i = 0; i + 1 < u.size(); ++i) out << u[i] << ", "; if (!u.empty()) out << u.back(); return out << '}'; }
template <class U, class V>   scan_op(pair <U, V>)  { return in >> u.fi >> u.se; }
template <class U, class V>  print_op(pair <U, V>)  { return out << '(' << u.fi << ", " << u.se << ')'; }

const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int dir[] = {1, 0, -1, 0, 1, 1, -1, -1, 1}; // {2, 1, -2, -1, -2, 1, 2, -1, 2};
const int MAX = 1002;

int numRow, numCol, numComp, inComp[MAX][MAX];
char grid[MAX][MAX];

bool inside(int x, int y) { return 1 <= x && x <= numRow && 1 <= y && y <= numCol && grid[x][y] != '*'; }

void init(void) {
	cin >> numRow >> numCol;
	for (int i = 1; i <= numRow; ++i)
		for (int j = 1; j <= numCol; ++j)
			cin >> grid[i][j];
}

void bfs(int s, int t) {
	++numComp;
	inComp[s][t] = numComp;
	queue <pair <int, int>> q;
	q.push(make_pair(s, t));
	while (!q.empty()) {
		auto [u, v] = q.front(); q.pop();
		for (int d = 0; d < 4; ++d) {
			int x = u + dir[d];
			int y = v + dir[d + 1];
			if (inside(x, y) && !inComp[x][y] && grid[x][y] == grid[s][t]) {
				inComp[x][y] = numComp;
				q.push(make_pair(x, y));
			}
		}
	}
}

vector <int> adj[MAX * MAX];
int dist[MAX * MAX];

void process(void) {
	for (int i = 1; i <= numRow; ++i)
		for (int j = 1; j <= numCol; ++j)
			if (inside(i, j) && !inComp[i][j]) bfs(i, j);
	for (int x = 1; x <= numRow; ++x) for (int y = 1; y <= numCol; ++y) if (inside(x, y)) for (int d = 0; d < 4; ++d) {
		int u = x + dir[d];
		int v = y + dir[d + 1];
		if (!inside(u, v) || inComp[x][y] == inComp[u][v]) continue;
		adj[inComp[x][y]].push_back(inComp[u][v]);
	}
	for (int i = 1; i <= numComp; ++i) {
		sort(adj[i].begin(), adj[i].end());
		adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
	}
	queue <int> q;
	dist[1] = 1;
	q.push(1);
	while (true) {
		int u = q.front(); q.pop();
		for (int v: adj[u]) if (!dist[v]) {
			dist[v] = dist[u] + 1;
			q.push(v);
		}
		if (q.empty()) return void(cout << dist[u] << '\n');
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("coci1920_r1_zoo");
	init();
	process();
	// cerr << "Time elapsed: " << TIME << " s.\n";
	return (0^0);
}

Compilation message (stderr)

zoo.cpp: In function 'int main()':
zoo.cpp:22:69: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zoo.cpp:95:2: note: in expansion of macro 'file'
   95 |  file("coci1920_r1_zoo");
      |  ^~~~
zoo.cpp:22:103: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define          file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                                                               ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
zoo.cpp:95:2: note: in expansion of macro 'file'
   95 |  file("coci1920_r1_zoo");
      |  ^~~~

• Subtask 1: 45 / 45
• Subtask 2: 65 / 65