oj.uz

Submission #144161

# Submission time Handle Problem Language Result Execution time Memory
144161 2019-08-16T08:27:28 Z emilem Izlet (COI19_izlet) C++14
43 / 100
 1295 ms 54156 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 638 ms 36088 KB Output is correct
3 Correct 630 ms 36088 KB Output is correct
4 Correct 644 ms 37112 KB Output is correct
5 Correct 641 ms 38264 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 35832 KB Output is correct
2 Correct 620 ms 35704 KB Output is correct
3 Correct 1239 ms 35960 KB Output is correct
4 Correct 1295 ms 36028 KB Output is correct
5 Correct 608 ms 35832 KB Output is correct
6 Correct 730 ms 35832 KB Output is correct
7 Correct 538 ms 25744 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 638 ms 36088 KB Output is correct
3 Correct 630 ms 36088 KB Output is correct
4 Correct 644 ms 37112 KB Output is correct
5 Correct 641 ms 38264 KB Output is correct
6 Correct 610 ms 35832 KB Output is correct
7 Correct 620 ms 35704 KB Output is correct
8 Correct 1239 ms 35960 KB Output is correct
9 Correct 1295 ms 36028 KB Output is correct
10 Correct 608 ms 35832 KB Output is correct
11 Correct 730 ms 35832 KB Output is correct
12 Correct 538 ms 25744 KB Output is correct
13 Incorrect 643 ms 54156 KB Unexpected end of file - int32 expected
14 Halted 0 ms 0 KB -