Submission #305321

#	Time	Username	Problem	Language	Result	Execution time	Memory
305321		JustInCase	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	255 ms	22396 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <iostream>

#define int32_t int
#define int64_t long long

const int32_t MAX_N = 1000;

struct Dsu {
	int32_t parent[MAX_N + 5], siz[MAX_N + 5];	
	
	void init(int32_t n) {
		for(int32_t i = 0; i < n; i++) {
			parent[i] = i;
			siz[i] = 1;
		}
	}

	void unite(int32_t x, int32_t y) {
		if(siz[x] < siz[y]) {
			parent[x] = y;
			siz[y] += siz[x];
		}
		else {
			parent[y] = x;
			siz[x] += siz[y];
		}
	}

	int32_t find_parent(int32_t x) {
		if(parent[x] == x) {
			return x;
		}
		
		parent[x] = find_parent(parent[x]);
		return parent[x];
	}
};

Dsu dsuLoops, dsuBranches;

int32_t construct(std::vector< std::vector< int32_t > > p) {
	int32_t n = p.size();

	dsuLoops.init(n);
	dsuBranches.init(n);

	for(int32_t i = 0; i < n; i++) {
		for(int32_t j = i + 1; j < n; j++) {
			if(p[i][j] == 3) {
				return 0;
			}

			if(p[i][j] == 1) {
				int32_t parI = dsuBranches.find_parent(i);
				int32_t parJ = dsuBranches.find_parent(j);

				if(parI != parJ) {
					dsuBranches.unite(parI, parJ);
				}
			}
		}
	}
	
	std::vector< std::vector< int32_t > > branches(n);
	std::vector< int32_t > roots;
	for(int32_t i = 0; i < n; i++) {
		branches[dsuBranches.find_parent(i)].push_back(i);
	}

	std::vector< std::vector< int32_t > > res(n, std::vector< int32_t >(n, 0)); 
	for(int32_t i = 0; i < n; i++) {
		if(branches[i].size() > 0) {
			for(int32_t a = 0; a < branches[i].size(); a++) {
				for(int32_t b = a + 1; b < branches[i].size(); b++) {
					if(p[branches[i][a]][branches[i][b]] != 1) {
						return 0;
					}
				}
			}

			roots.push_back(i);
			for(int32_t j = 1; j < branches[i].size(); j++) {
				res[branches[i][j - 1]][branches[i][j]] = res[branches[i][j]][branches[i][j - 1]] = 1;
			}
		}
	}

	for(int32_t i = 0; i < roots.size(); i++) {
		for(int32_t j = i + 1; j < roots.size(); j++) {
			if(p[roots[i]][roots[j]] == 2) {
				int32_t parI = dsuLoops.find_parent(roots[i]);
				int32_t parJ = dsuLoops.find_parent(roots[j]);

				if(parI != parJ) {
					dsuLoops.unite(parI, parJ);
				}
			}
		}
	}

	std::vector< std::vector< int32_t > > loops(n);
	for(int32_t i = 0; i < n; i++) {
		int32_t par = dsuLoops.find_parent(i);

		loops[par].push_back(i);
	}
	
	/**
	for(int32_t i = 0; i < n; i++) {
		std::cout << i << ": ";
		for(auto &x : loops[i]) {
			std::cout << x << " ";
		}
		std::cout << '\n';
	}
	*/

	for(int32_t i = 0; i < n; i++) {
		if(loops[i].size() == 2) {
			return 0;
		}
		
		for(int32_t a = 0; a < loops[i].size(); a++) {
			for(int32_t b = a + 1; b < loops[i].size(); b++) {
				if(p[loops[i][a]][loops[i][b]] != 2) {
					return 0;
				}
			}
		}

		if(loops[i].size() > 2) {
			for(int32_t j = 0; j < loops[i].size() - 1; j++) {
				res[loops[i][j]][loops[i][j + 1]] = res[loops[i][j + 1]][loops[i][j]] = 1;
			}
			res[loops[i][0]][loops[i].back()] = res[loops[i].back()][loops[i][0]] = 1;
		}
	}
	
	build(res);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:75:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |    for(int32_t a = 0; a < branches[i].size(); a++) {
      |                       ~~^~~~~~~~~~~~~~~~~~~~
supertrees.cpp:76:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int32_t b = a + 1; b < branches[i].size(); b++) {
      |                            ~~^~~~~~~~~~~~~~~~~~~~
supertrees.cpp:84:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |    for(int32_t j = 1; j < branches[i].size(); j++) {
      |                       ~~^~~~~~~~~~~~~~~~~~~~
supertrees.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for(int32_t i = 0; i < roots.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
supertrees.cpp:91:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   for(int32_t j = i + 1; j < roots.size(); j++) {
      |                          ~~^~~~~~~~~~~~~~
supertrees.cpp:125:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |   for(int32_t a = 0; a < loops[i].size(); a++) {
      |                      ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:126:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |    for(int32_t b = a + 1; b < loops[i].size(); b++) {
      |                           ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:134:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |    for(int32_t j = 0; j < loops[i].size() - 1; j++) {
      |                       ~~^~~~~~~~~~~~~~~~~~~~~

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