Submission #305318

#	Time	Username	Problem	Language	Result	Execution time	Memory
305318		JustInCase	Connecting Supertrees (IOI20_supertrees)	C++17	19 / 100	259 ms	22136 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;

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

	dsuLoops.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] == 2) {
				int32_t parI = dsuLoops.find_parent(i);
				int32_t parJ = dsuLoops.find_parent(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';
	}
	*/

	std::vector< std::vector< int32_t > > res(n, std::vector< int32_t >(n, 0)); 
	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:88:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for(int32_t a = 0; a < loops[i].size(); a++) {
      |                      ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:89:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |    for(int32_t b = a + 1; b < loops[i].size(); b++) {
      |                           ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:97:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |    for(int32_t j = 0; j < loops[i].size() - 1; j++) {
      |                       ~~^~~~~~~~~~~~~~~~~~~~~

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