Submission #144741

#	Time	Username	Problem	Language	Result	Execution time	Memory
144741		emilem	Izlet (COI19_izlet)	C++14	100 / 100	963 ms	90368 KiB

izlet

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;

vector< vector<int> > a;
vector< vector<int> > nei, grpNei;
int maxColor = 0;
vector<bool> used;
vector<int> group;
vector<int> color;
vector<bool> met;
vector< vector<int> > groups;

void Dfs(int v, vector<int>& group)
{
	group.push_back(v);
	used[v] = true;
	for (int i = 0; i < nei[v].size(); ++i)
		if (!used[nei[v][i]])
			Dfs(nei[v][i], group);
}
void Tree(int grp)
{
	used[grp] = true;
	for (int i = 0; i < grpNei[grp].size(); ++i)
	{
		int to = grpNei[grp][i];
		if (used[to])
			continue;
		nei[grp].push_back(to);
		nei[to].push_back(grp);
		Tree(to);
	}
}
int FindColor(int grp, int prev, int src)
{
	if (a[groups[src][0]][groups[grp][0]] == a[groups[src][0]][groups[prev][0]] && !met[color[grp]])
		return color[grp];
	met[color[grp]] = true;
	for (int i = 0; i < nei[grp].size(); ++i)
	{
		int to = nei[grp][i];
		if (color[to] != -1 && to != prev)
		{
			int res = FindColor(to, grp, src);
			if (res != -1)
				return res;
		}
	}
	return -1;
}
void Solve(int grp)
{
	fill(met.begin(), met.end(), false);
	for (int i = 0; i < nei[grp].size(); ++i)
		if (color[nei[grp][i]] != -1)
		{
			color[grp] = FindColor(nei[grp][i], grp, grp);
			break;
		}
	if (color[grp] == -1)
		color[grp] = ++maxColor;
	for (int i = 0; i < nei[grp].size(); ++i)
	{
		int to = nei[grp][i];
		if (color[to] == -1)
			Solve(to);
	}
}
void SolveAll()
{
	nei.resize(a.size());
	used.resize(a.size(), false);
	for (int i = 0; i < a.size(); ++i)
		for (int j = 0; j < a.size(); ++j)
			if (a[i][j] == 1 && i != j)
				nei[i].push_back(j);
	for (int i = 0; i < a.size(); ++i)
		if (!used[i])
		{
			groups.push_back(vector<int>());
			Dfs(i, groups.back());
			for (int j = 0; j < groups.back().size(); ++j)
				group[groups.back()[j]] = groups.size() - 1;
		}
	grpNei.resize(groups.size());
	for (int i = 0; i < a.size(); ++i)
		for (int j = 0; j < a.size(); ++j)
			if (a[i][j] == 2 && i != j)
				grpNei[group[i]].push_back(group[j]);
	fill(nei.begin(), nei.end(), vector<int>());
	nei.resize(groups.size());
	fill(used.begin(), used.end(), false);
	used.resize(groups.size());
	Tree(0);
	color.resize(groups.size(), -1);
	met.resize(groups.size());
	Solve(0);
	for (int i = 0; i < a.size(); ++i)
		cout << color[group[i]] << ' ';
	cout << endl;
	for (int i = 0; i < groups.size(); ++i)
		for (int j = 0; j + 1 < groups[i].size(); ++j)
			cout << groups[i][j] + 1 << ' ' << groups[i][j + 1] + 1 << '\n';
	for (int i = 0; i < groups.size(); ++i)
		for (int j = 0; j < nei[i].size(); ++j)
		{
			int to = nei[i][j];
			if (i < to)
				cout << groups[i][0] + 1 << ' ' << groups[to][0] + 1 << '\n';
		}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int subTask;
	cin >> subTask;
	int n;
	cin >> n;
	a.resize(n, vector<int>(n));
	group.resize(n);
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			cin >> a[i][j];
	SolveAll();

	char I;
	cin >> I;
}
/*
2
5
1 2 2 2 2
2 1 3 3 2
2 3 1 2 3
2 3 2 1 3
2 2 3 3 1
*/

Compilation message (stderr)

izlet.cpp: In function 'void Dfs(int, std::vector<int>&)':
izlet.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < nei[v].size(); ++i)
                  ~~^~~~~~~~~~~~~~~
izlet.cpp: In function 'void Tree(int)':
izlet.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < grpNei[grp].size(); ++i)
                  ~~^~~~~~~~~~~~~~~~~~~~
izlet.cpp: In function 'int FindColor(int, int, int)':
izlet.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < nei[grp].size(); ++i)
                  ~~^~~~~~~~~~~~~~~~~
izlet.cpp: In function 'void Solve(int)':
izlet.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < nei[grp].size(); ++i)
                  ~~^~~~~~~~~~~~~~~~~
izlet.cpp:65:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < nei[grp].size(); ++i)
                  ~~^~~~~~~~~~~~~~~~~
izlet.cpp: In function 'void SolveAll()':
izlet.cpp:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); ++i)
                  ~~^~~~~~~~~~
izlet.cpp:77:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < a.size(); ++j)
                   ~~^~~~~~~~~~
izlet.cpp:80:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); ++i)
                  ~~^~~~~~~~~~
izlet.cpp:85:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < groups.back().size(); ++j)
                    ~~^~~~~~~~~~~~~~~~~~~~~~
izlet.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); ++i)
                  ~~^~~~~~~~~~
izlet.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < a.size(); ++j)
                   ~~^~~~~~~~~~
izlet.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); ++i)
                  ~~^~~~~~~~~~
izlet.cpp:104:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < groups.size(); ++i)
                  ~~^~~~~~~~~~~~~~~
izlet.cpp:105:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j + 1 < groups[i].size(); ++j)
                   ~~~~~~^~~~~~~~~~~~~~~~~~
izlet.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < groups.size(); ++i)
                  ~~^~~~~~~~~~~~~~~
izlet.cpp:108:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < nei[i].size(); ++j)
                   ~~^~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57