답안 #736141

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
736141	2023-05-05T09:03:04 Z	marvinthang	Zoo (COCI19_zoo)	C++17	110 / 110	156 ms	39092 KB

/*************************************
*    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

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.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	23892 KB	Output is correct
2	Correct	12 ms	23920 KB	Output is correct
3	Correct	13 ms	24020 KB	Output is correct
4	Correct	14 ms	24120 KB	Output is correct
5	Correct	14 ms	24404 KB	Output is correct
6	Correct	14 ms	24404 KB	Output is correct
7	Correct	14 ms	24440 KB	Output is correct
8	Correct	15 ms	24404 KB	Output is correct
9	Correct	13 ms	24404 KB	Output is correct
10	Correct	14 ms	24440 KB	Output is correct
11	Correct	15 ms	24404 KB	Output is correct
12	Correct	15 ms	24404 KB	Output is correct
13	Correct	14 ms	24264 KB	Output is correct
14	Correct	18 ms	24404 KB	Output is correct
15	Correct	14 ms	24304 KB	Output is correct

Subtask #2
65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	23892 KB	Output is correct
2	Correct	12 ms	23920 KB	Output is correct
3	Correct	13 ms	24020 KB	Output is correct
4	Correct	14 ms	24120 KB	Output is correct
5	Correct	14 ms	24404 KB	Output is correct
6	Correct	14 ms	24404 KB	Output is correct
7	Correct	14 ms	24440 KB	Output is correct
8	Correct	15 ms	24404 KB	Output is correct
9	Correct	13 ms	24404 KB	Output is correct
10	Correct	14 ms	24440 KB	Output is correct
11	Correct	15 ms	24404 KB	Output is correct
12	Correct	15 ms	24404 KB	Output is correct
13	Correct	14 ms	24264 KB	Output is correct
14	Correct	18 ms	24404 KB	Output is correct
15	Correct	14 ms	24304 KB	Output is correct
16	Correct	35 ms	29780 KB	Output is correct
17	Correct	33 ms	29816 KB	Output is correct
18	Correct	33 ms	29972 KB	Output is correct
19	Correct	38 ms	29888 KB	Output is correct
20	Correct	34 ms	29772 KB	Output is correct
21	Correct	145 ms	38444 KB	Output is correct
22	Correct	144 ms	38344 KB	Output is correct
23	Correct	145 ms	38512 KB	Output is correct
24	Correct	155 ms	39092 KB	Output is correct
25	Correct	156 ms	38916 KB	Output is correct
26	Correct	141 ms	38744 KB	Output is correct
27	Correct	138 ms	38368 KB	Output is correct
28	Correct	140 ms	38296 KB	Output is correct
29	Correct	146 ms	38988 KB	Output is correct
30	Correct	144 ms	38784 KB	Output is correct

답안 #736141

Compilation message

Subtask #1 45.0 / 45.0

Subtask #2 65.0 / 65.0

Subtask #1
45.0 / 45.0

Subtask #2
65.0 / 65.0