Submission #570610

#	Time	Username	Problem	Language	Result	Execution time	Memory
570610		aryan12	Clickbait (COCI18_clickbait)	C++17	120 / 120	20 ms	2244 KiB

clickbait

#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e3 + 5;
int n, m;
char a[N][N];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

array<int, 2> FindPipe(int x, int y, int next_dir)
{
	array<int, 2> prev_pos = {x, y};
	x += dx[next_dir];
	y += dy[next_dir];
	int _x, _y;
	while(true)
	{
		// cout << "x = " << x << ", y = " << y << endl;
		// cout << "prev_pos = {" << prev_pos[0] << ", " << prev_pos[1] << "}" << endl;
		int cnt = 0;
		for(int i = 0; i < 4; i++)
		{
			if(x + dx[i] <= 0 || x + dx[i] > n || y + dy[i] <= 0 || y + dy[i] > m)
			{
				continue;
			}
			if(a[x + dx[i]][y + dy[i]] == '-' || a[x + dx[i]][y + dy[i]] == '|' || a[x + dx[i]][y + dy[i]] == '+')
			{
				cnt++;
			}
		}
		// cout << "cnt = " << cnt << endl;
		if(cnt >= 3)
		{
			_x = x, _y = y;
			break;
		}
		for(int i = 0; i < 4; i++)
		{
			// cout << x + dx[i] << ", " << y + dy[i] << endl;
			if(x + dx[i] <= 0 || x + dx[i] > n || y + dy[i] <= 0 || y + dy[i] > m)
			{
				continue;
			}
			// cout << "hello" << endl;
			if(a[x + dx[i]][y + dy[i]] != '.' && (x + dx[i] != prev_pos[0] || y + dy[i] != prev_pos[1]))
			{
				prev_pos = {x, y};
				x += dx[i], y += dy[i];
				break;
			}
		}
	}
	while(a[_x][_y] != '+')
	{
		_y--;
	}
	return {_x, _y};
}

void Component(int _i, int _j, int parent)
{
	// cout << "Component(" << _i << " " << _j << ") -> " << parent << endl;
	int pos_x = 0, pos_y;
	// Finding top left and bottom right corner of the rectangle component
	for(int j = _j + 1; j <= m; j++)
	{
		if(a[_i][j] == '+')
		{
			pos_y = j;
			break;
		}
	}
	assert(pos_y != 0);
	for(int i = _i + 1; i <= n; i++)
	{
		if(a[i][pos_y] == '+')
		{
			pos_x = i;
			break;
		}
	}
	assert(pos_x != 0);
	// cout << "pos_x = " << pos_x << ", pos_y = " << pos_y << endl;
	// component top left: (_i, _j)
	// component bottom right: (pos_x, pos_y)

	// Finding the number of the rectangle component
	int current_number = 0;
	for(int i = _i; i <= pos_x; i++)
	{
		for(int j = _j; j <= pos_y; j++)
		{
			if(a[i][j] >= '0' && a[i][j] <= '9')
			{
				current_number = (current_number * 10) + (a[i][j] - '0');
			}
		}
	}
	// cout << "current_number = " << current_number << endl;
	assert(current_number != 0);

	// Finding pipes (if any) connected to the component, and the components to which the pipe leads to
	for(int i = pos_x; i >= _i; i--)
	{
		if(_j != 0 && a[i][_j - 1] == '-')
		{
			// cout << "Found at (left hand side) pos: (" << i << ", " << _j << ") " << endl;
			array<int, 2> top_left = FindPipe(i, _j, 3);
			Component(top_left[0], top_left[1], current_number);
		}
		if(pos_y != m && a[i][pos_y + 1] == '-')
		{
			// cout << "Found at (right hand side) pos: (" << i << ", " << pos_y << ") " << endl;
			array<int, 2> top_left = FindPipe(i, pos_y, 1);
			Component(top_left[0], top_left[1], current_number);
		}
	}
	cout << current_number << "\n";
}

void Solve() 
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			cin >> a[i][j];
		}
	}
	bool flag = false;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			if(a[i][j] == '+')
			{
				Component(i, j, 0);
				flag = true;
				break;
			}
		}
		if(flag == true)
		{
			break;
		}
	}
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Compilation message (stderr)

clickbait.cpp: In function 'void Component(long long int, long long int, long long int)':
clickbait.cpp:115:3: warning: 'pos_y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  115 |   if(pos_y != m && a[i][pos_y + 1] == '-')
      |   ^~

• Subtask 1: 120 / 120