Submission #1039704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039704		parsadox2	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	187 ms	28092 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;
int n;
vector <vector<int>> answer , p;
vector <int> all , all1;
bool flg , marked[N] , vis[N];

void Dfs(int v)
{
	marked[v] = true;
	all.push_back(v);
	for(int i = 0 ; i < n ; i++)  if(p[v][i] != 0 && !marked[i])
		Dfs(i);
}

bool check(vector <int> vec)
{
	bool res = true;
	for(auto u : vec)  for(auto v : vec)  if(p[u][v] != 1)
		res = false;
	for(int i = 1 ; i < vec.size() ; i++)
	{
		answer[vec[i]][vec[i - 1]] = 1;
		answer[vec[i - 1]][vec[i]] = 1;
	}
	return res;
}

void Dfs1(int v)
{
	vis[v] = true;
	all1.push_back(v);
	for(int i = 0 ; i < n ; i++)  if(p[v][i] == 1 && !vis[i])
		Dfs1(i);
}

void Solve()
{
	for(auto u : all)  for(auto v : all)  if(p[u][v] == 0 || p[u][v] == 3)
	{
		flg = false;
		return;
	}
	vector <vector<int>> cmp;
	for(auto u : all)  if(!vis[u])
	{
		all1.clear();
		Dfs1(u);
		if(!check(all1))
			flg = false;
		cmp.push_back(all1);
	}
	if(cmp.size() == 2)
	{
		flg = false;
		return;
	}
	if(cmp.size() == 1)
		return;
	for(int i = 1 ; i < cmp.size() ; i++)
	{
		answer[cmp[i].back()][cmp[i - 1].back()] = 1;
		answer[cmp[i - 1].back()][cmp[i].back()] = 1;
	}
	answer[cmp[cmp.size() - 1].back()][cmp[0].back()] = 1;
	answer[cmp[0].back()][cmp[cmp.size() - 1].back()] = 1;
}

int construct(vector<vector<int>> inp) {
	flg = true;
	p = inp;
	n = p.size();
	for (int i = 0; i < n; i++) {
		vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	for(int i = 0 ; i < n ; i++)  if(!marked[i])
	{
		all.clear();
		Dfs(i);
		Solve();
	}
	if(!flg)
		return 0;
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'bool check(std::vector<int>)':
supertrees.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i = 1 ; i < vec.size() ; i++)
      |                  ~~^~~~~~~~~~~~
supertrees.cpp: In function 'void Solve()':
supertrees.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int i = 1 ; i < cmp.size() ; i++)
      |                  ~~^~~~~~~~~~~~

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