Submission #144161

#	Time	Username	Problem	Language	Result	Execution time	Memory
144161		emilem	Izlet (COI19_izlet)	C++14	43 / 100	1295 ms	54156 KiB

izlet

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

vector< vector<int> > a;

namespace Subtask1
{
	vector< vector<int> > nei;
	vector<bool> used;

	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 Solve1()
	{
		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);
		vector< vector<int> > groups;
		for (int i = 0; i < a.size(); ++i)
			if (!used[i])
			{
				groups.push_back(vector<int>());
				Dfs(i, groups.back());
			}
		vector<int> ans(a.size());
		for (int i = 0; i < groups.size(); ++i)
			for (int j = 0; j < groups[i].size(); ++j)
				ans[groups[i][j]] = (i % 2) + 1;
		for (int i = 0; i < ans.size(); ++i)
			cout << ans[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';
			if (i + 1 < groups.size())
				cout << groups[i].back() + 1 << ' ' << groups[i + 1][0] + 1 << '\n';
		}
	}
}
void Subtask2()
{
	vector<int> ans(a.size(), -1);
	ans[0] = 1;
	for (int i = 1; i < a.size(); ++i)
	{
		set<int> s;
		for (int j = i - 1; j >= 0; --j)
		{
			s.insert(ans[j]);
			if (s.size() == a[j][i])
			{
				ans[i] = ans[j];
				break;
			}
		}
		if (ans[i] == -1)
			ans[i] = *max_element(ans.begin(), ans.begin() + i) + 1;
	}
	for (int i = 0; i < a.size(); ++i)
		cout << ans[i] << ' ';
	cout << endl;
	for (int i = 1; i < a.size(); ++i)
		cout << i << ' ' << i + 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));
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			cin >> a[i][j];
	if (subTask == 1)
		Subtask1::Solve1();
	else if (subTask == 2)
		Subtask2();


	char I;
	cin >> I;
}

Compilation message (stderr)

izlet.cpp: In function 'void Subtask1::Dfs(int, std::vector<int>&)':
izlet.cpp:18:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < nei[v].size(); ++i)
                   ~~^~~~~~~~~~~~~~~
izlet.cpp: In function 'void Subtask1::Solve1()':
izlet.cpp:26:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size(); ++i)
                   ~~^~~~~~~~~~
izlet.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < a.size(); ++j)
                    ~~^~~~~~~~~~
izlet.cpp:31:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size(); ++i)
                   ~~^~~~~~~~~~
izlet.cpp:38:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < groups.size(); ++i)
                   ~~^~~~~~~~~~~~~~~
izlet.cpp:39:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < groups[i].size(); ++j)
                    ~~^~~~~~~~~~~~~~~~~~
izlet.cpp:41:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < ans.size(); ++i)
                   ~~^~~~~~~~~~~~
izlet.cpp:44:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < groups.size(); ++i)
                   ~~^~~~~~~~~~~~~~~
izlet.cpp:46:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j + 1 < groups[i].size(); ++j)
                    ~~~~~~^~~~~~~~~~~~~~~~~~
izlet.cpp:48:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i + 1 < groups.size())
        ~~~~~~^~~~~~~~~~~~~~~
izlet.cpp: In function 'void Subtask2()':
izlet.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < a.size(); ++i)
                  ~~^~~~~~~~~~
izlet.cpp:63:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (s.size() == a[j][i])
izlet.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); ++i)
                  ~~^~~~~~~~~~
izlet.cpp:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < a.size(); ++i)
                  ~~^~~~~~~~~~

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