Submission #240118

#	Time	Username	Problem	Language	Result	Execution time	Memory
240118		MrRobot_28	Clickbait (COCI18_clickbait)	C++17	120 / 120	95 ms	6392 KiB

clickbait

#include <bits/stdc++.h>
                  
using namespace std;
vector <int> ans;
vector <vector <pair <int, int> > > g;
bool cmp(pair <int, int> a, pair <int, int> b)
{
	return a.second > b.second;
}
void dfs(int v)
{
	for(int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i].first;
		dfs(to);
	}
	ans.push_back(v);
}
signed main(){
//	ios_base::sync_with_stdio(false);
//	cin.tie(NULL);
//	cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	int n1 = 0;
	vector <vector <int> > colored(n, vector <int> (m, -1));
	vector <vector <char> > A(n, vector <char> (m));
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			cin >> A[i][j];
		}
	}
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			int c = 0;
			if(A[i][j] >= '0' && A[i][j] <= '9')
			{
				if(j == 0 || A[i][j - 1] < '0' || A[i][j - 1] > '9')
				{
					n1++;
					for(int d = j; d < m; d++)
					{
						if(A[i][d] >= '0' && A[i][d] <= '9')
						{
							c = c * 10 + A[i][d] - '0';
						}
						else
						{
							break;
						}
					}
					c--;
					queue <pair <int, int> > Q;
					Q.push({i, j});
					colored[i][j] = c;
					while(Q.size() != 0)
					{
						int x = Q.front().first;
						int y = Q.front().second;
						Q.pop();
						if(x > 0 && A[x - 1][y] != '-' && colored[x - 1][y] == -1)
						{
							colored[x - 1][y] = c;
							Q.push({x - 1, y});
						}
						else if(x > 0)
						{
							colored[x - 1][y] = c;
						}
						if(x < n - 1 && A[x + 1][y] != '-' && colored[x + 1][y] == -1)
						{
							colored[x + 1][y] = c;
							Q.push({x + 1, y});
						}
						else if(x < n - 1)
						{
							colored[x + 1][y] = c;
						}
						if(y > 0 && A[x][y - 1] != '|' && colored[x][y - 1] == -1)
						{
							colored[x][y - 1] = c;
							Q.push({x, y - 1});
						}
						else if(y > 0)
						{
							colored[x][y - 1] = c;
						}
						if(y < m - 1 && A[x][y + 1] != '|' && colored[x][y + 1] == -1)
						{
							colored[x][y + 1] = c;
							Q.push({x, y + 1});
						}
						else if(y < m- 1)
						{
							colored[x][y + 1] = c;
						}
						
						if(x > 0 && y > 0 && A[x - 1][y- 1] == '+')
						{
							colored[x - 1][y - 1] = c;
						}
						if(x > 0 && y < m - 1 && A[x - 1][y + 1] == '+')
						{
							colored[x - 1][y + 1] = c;
						}
						if(x < n - 1 && y > 0 && A[x + 1][y - 1] == '+')
						{
							colored[x + 1][y - 1] = c; 
						}
						if(x < n - 1 && y < m - 1 && A[x + 1][y + 1] == '+')
						{
							colored[x + 1][y + 1] = c;
						}
					}
				}
			}
		}
	}
	g.resize(n1);
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			if(colored[i][j] != -1)
			{
				continue;
			}
			if(A[i][j] == '-' || A[i][j] == '+' || A[i][j] == '|')
			{
				queue <pair <int, int> > q;
				int c1 = -1, c2 = -1;
				pair <int, int> x1, x2;
				q.push({i, j});
				colored[i][j] = 1e9;
				while(q.size() != 0)
				{
					int x = q.front().first;
					int y = q.front().second;
					q.pop();
					if(x > 0 && A[x - 1][y] != '.' && colored[x - 1][y] == -1)
					{
						colored[x - 1][y] = 1e9;
						q.push({x - 1, y});
					}
					else if(x > 0 && A[x - 1][y] != '.' && colored[x - 1][y] != 1e9)
					{
						if(c1 == -1)
						{
							c1 = colored[x - 1][y];
							x1 = {x - 1, y};
						}
						else
						{
							c2 = colored[x - 1][y];
							x2 = {x - 1, y};
						}
					}
					if(x < n - 1 && A[x + 1][y] != '.' && colored[x + 1][y] == -1)
					{
						colored[x + 1][y] = 1e9;
						q.push({x + 1, y});
					}
					else if(x < n - 1 && A[x + 1][y] != '.' && colored[x + 1][y] != 1e9)
					{
						if(c1 == -1)
						{
							c1 = colored[x + 1][y];
							x1 = {x + 1, y};
						}
						else
						{
							c2 = colored[x + 1][y];
							x2 = {x + 1, y};
						}
					}
					if(y > 0 && A[x][y - 1] != '.' && colored[x][y - 1] == -1)
					{
						colored[x][y - 1] = 1e9;
						q.push({x, y - 1});
					}
					else if(y > 0 && A[x][y - 1] != '.' && colored[x][y - 1] != 1e9)
					{
						if(c1 == -1)
						{
							c1 = colored[x][y - 1];
							x1 = {x, y - 1};
						}
						else
						{
							c2 = colored[x][y - 1];
							x2 = {x, y - 1};
						}
					}
					if(y < m - 1 && A[x][y + 1] != '.' && colored[x][y + 1] == -1)
					{
						colored[x][y + 1] = 1e9;
						q.push({x, y + 1});
					}
					else if(y < m - 1 && A[x][y + 1] != '.' && colored[x][y + 1] != 1e9)
					{
						if(c1 == -1)
						{
							c1 = colored[x][y + 1];
							x1 = {x, y + 1};
						}
						else
						{
							c2 = colored[x][y + 1];
							x2 = {x, y + 1};
						}
					}
				}
				if(x1.first > x2.first)
				{
					swap(c1, c2);
					swap(x1, x2);
				}
				g[c1].push_back({c2, x1.first});
			}
		}
	}
	for(int i= 0; i < n1; i++)
	{
		sort(g[i].begin(), g[i].end(), cmp);
	}
	dfs(0);
	for(int i = 0; i < ans.size(); i++)
	{
		cout << ans[i] + 1 << "\n";
	}
	return 0;
}

Compilation message (stderr)

clickbait.cpp: In function 'void dfs(int)':
clickbait.cpp:12:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[v].size(); i++)
                 ~~^~~~~~~~~~~~~
clickbait.cpp: In function 'int main()':
clickbait.cpp:231:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ans.size(); i++)
                 ~~^~~~~~~~~~~~

• Subtask 1: 120 / 120