oj.uz

Submission #1032876

# Submission time Handle Problem Language Result Execution time Memory
1032876 2024-07-24T10:16:33 Z fv3 Connecting Supertrees (IOI20_supertrees) C++14
0 / 100
 0 ms 348 KB 
#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

int construct(vector<vector<int>> p) 
{
	int n = p.size();

	for (int i = 0; i < n; i++)
		p[i].push_back(i);
	sort(p.begin(), p.end());

	// 1. Find all parts which are the same
	vector<vector<int>> parts = { {p[0].back()} };
	map<vector<int>, vector<int>> cycles;

	int l = 0, r = 1;
	while (r < n)
	{
		int i = 0;
		for (; i < n; i++)
		{
			if (p[r-1][i] != p[r][i])
				break;
		}

		if (i != n)
		{
			parts.push_back({p[r].back()});

			// Count 1's in last part
			int one_cnt = 0;
			for (int j = 0; j < n; j++)
			{
				if (p[r-1][j] == 1)
					one_cnt++;
			}

			if (one_cnt != r - l)
				return 0;

			vector<int> bs(n);
			for (int j = 0; j < n; j++)
			{
				if (p[r-1][j]) 
					bs[j] = 1;
			}

			cycles[bs].push_back(r-1);
			l = r;
		}
		else
		{
			parts.back().push_back(p[r].back());
		}

		r++;
	}

	// Count 1's in last part
	int one_cnt = 0;
	for (int j = 0; j < n; j++)
	{
		if (p[r-1][j] == 1)
			one_cnt++;
	}

	if (one_cnt != r - l)
		return 0;

	vector<int> bs(n);
	for (int j = 0; j < n; j++)
	{
		if (p[r-1][j]) 
			bs[j] = 1;
	}
	cycles[bs].push_back(r-1);

	cout << parts.size() << '\n' << cycles.size() << '\n';

	// 2. Generate parts
	vector<vector<int>> answer(n, vector<int>(n));
	for (auto path : parts)
	{
		for (int i = 1; i < path.size(); i++)
		{
			answer[path[i]][path[i-1]] = 1;
			answer[path[i-1]][path[i]] = 1;
		}
	}

	// 3. Generate cycles

	// 4. Profit
	build(answer);
	return 1;
}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:86:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for (int i = 1; i < path.size(); i++)
      |                   ~~^~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB secret mismatch
2 Halted 0 ms 0 KB -