Submission #675548

#	Time	Username	Problem	Language	Result	Execution time	Memory
675548		speedyArda	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	189 ms	24120 KiB

supertrees

#include "supertrees.h"
//#include <vector>
#define vi vector<int>
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 1005;
int par[MAXN];
int twos[MAXN];
vector<vector<int> > elems(MAXN);

auto cmp = [](int a, int b)
{
	//cout << a << " " << b << "\n";
	if(twos[a] != twos[b])
		return twos[a] > twos[b];
	else
		return a > b;
};
int findset(int a)
{
	if(par[a] == a)
		return a;
	return par[a] = findset(par[a]);
}
int mergeset(int a, int b)
{
	a = findset(a), b = findset(b);
	if(a == b)
		return 0;
	//if(a > b)
		//swap(a,b);
	par[b] = a;
	return a;	
}

int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> answer(n, vector<int>(n));
	for(int i = 0; i < n; i++) {
		par[i] = i;
		twos[i] = 0;
	}
	bool valid = true;
	for(int i = 0; i < n; i++)
	{
		if(findset(i) == i) // New component
		{
			//elems[i].push_back(i);
			for(int a = 0; a < n; a++)
			{

				if(p[i][a] == 0)
					continue;
				//cout << i << " " << a << "\n";
				if(findset(a) == a)
				{
					mergeset(i, a);
					elems[i].push_back(a);
				}
			}
		}
	}

	//bool valid = true;
	for(int i = 0; i < n; i++)
	{
		vi incycle;
		if(elems[i].size() == 0)
			continue;
		set<int, decltype(cmp)> curr(cmp);
		
		for(int a : elems[i])
		{
			for(int l = 0; l < elems[i].size(); l++)
			{
				if(p[a][elems[i][l]] == 2)
					twos[a]++;
			}
			//cout << a << ""
			curr.insert(a);
		}
		int lastelem = -1;

		while(!curr.empty())
		{
			int v = *(curr.begin());
			curr.erase(curr.begin());
			if(incycle.size() > 0)
			{
				lastelem = incycle.back();
				answer[v][lastelem] = answer[lastelem][v] = 1;
				
			}
			incycle.push_back(v);
			vi torem;
			torem.push_back(v);
			for(int a : curr)
			{	
				//cout << v << " " << a << " " << p[a][v] << "\n";
				if(p[v][a] == 1) {
					//cout << v << " " << a << "\n";
					answer[v][a] = answer[a][v] = 1;
					torem.push_back(a);
					//curr.erase(a);
				}
			}
			for(int l = 0; l < torem.size(); l++)
			{
				for(int a = 0; a < torem.size(); a++)
				{
					if(l == a)
						continue;
					if(p[torem[l]][torem[a]] != 1)
						valid = false;
				}
			}
			for(int e : torem) 
				curr.erase(e);
			
		}

		if(incycle.size() > 2) {
			answer[incycle.back()][incycle[0]] = answer[incycle[0]][incycle.back()] = 1;
		} else 
		{
			if(twos[incycle[0]] > 0)
				valid = false;

		}

		for(int l = 0; l < elems[i].size(); l++)
		{
			for(int a = 0; a < elems[i].size(); a++)
			{
				//if(elems[i][l] == elems[i][a])
					//continue;
				if(p[elems[i][l]][elems[i][a]] == 0)
					valid = false;
			}
		}
		for(int l = 0; l < incycle.size(); l++)
		{
			for(int a = 0; a < incycle.size(); a++)
			{
				if(incycle[l] == incycle[a])
					continue;
				if(p[incycle[l]][incycle[a]] != 2)
					valid = false;
			}
		}
		//else if(incycle.size() == 1)
			//valid = false;


	}

	for(int i = 0; i < n; i++)
	{
		for(int a = 0; a < n; a++)
		{
			if((findset(i) == findset(a) && p[i][a] == 0) || (findset(i) != findset(a) && p[i][a] != 0))
				valid = false;
		}
	}
	//if(incycle[i] != )
	if(valid) {
		build(answer);
		return 1;
	}
	else
		return 0;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:74:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |    for(int l = 0; l < elems[i].size(); l++)
      |                   ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:107:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |    for(int l = 0; l < torem.size(); l++)
      |                   ~~^~~~~~~~~~~~~~
supertrees.cpp:109:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for(int a = 0; a < torem.size(); a++)
      |                    ~~^~~~~~~~~~~~~~
supertrees.cpp:131:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |   for(int l = 0; l < elems[i].size(); l++)
      |                  ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:133:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |    for(int a = 0; a < elems[i].size(); a++)
      |                   ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:141:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |   for(int l = 0; l < incycle.size(); l++)
      |                  ~~^~~~~~~~~~~~~~~~
supertrees.cpp:143:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |    for(int a = 0; a < incycle.size(); a++)
      |                   ~~^~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4