Submission #1043745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043745		DeathIsAwe	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	109 ms	24200 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

int construct(vector<vector<int>> p) {
	int n = p.size(), prev;
	vector<vector<int>> ans(n), forest;
	vector<int> tree;
	bool visited[n];
	for (int i=0;i<n;i++) {
		visited[i] = false;
		for (int j=0;j<n;j++) {
			ans[i].push_back(0);
		}
	}



	for (int i=0;i<n;i++) {
		if (visited[i]) {
			continue;
		}
		visited[i] = true;
		tree.clear(); tree.push_back(i);
		for (int j=0;j<n;j++) {
			if (j == i) {
				continue;
			}
			if (p[i][j] == 1) {
				if (visited[j]) {
					return 0;
				}
				visited[j] = true;
				tree.push_back(j);
			} else if (p[i][j] == 3) {
				return 0;
			}
		}
		prev = i;
		for (int j: tree) {
			ans[prev][j] = 1;
			ans[j][prev] = 1;
			prev = j;
		}
		ans[i][i] = 0;
		for (int j: tree) {
			for (int k: tree) {
				if (p[j][k] != 1) {
					return 0;
				}
			}
		}
		forest.push_back(tree);
	}
	


	for (int i=0;i<n;i++) {
		visited[i] = false;
	}
	vector<int> group;
	vector<int> grouptags(forest.size(), -1);
	for (int i=0;i<forest.size();i++) {
		if (visited[forest[i][0]]) {
			continue;
		}
		visited[forest[i][0]] = true;
		group = {i};
		grouptags[i] = i;
		for (int j=i+1;j<forest.size();j++) {
			if (p[forest[i][0]][forest[j][0]] == 2) {
				visited[forest[j][0]] = true;
				group.push_back(j);
				grouptags[j] = i;
			}
		}
		//for (int j: group) {
		//	cout << j << ' ';
		//}
		//cout << '\n';
		if (group.size() == 2) {
			return 0;
		}
		for (int j: group) {
			for (int k=0;k<forest.size();k++) {
				if (j == k) {
					continue;
				}
				if (grouptags[k] != i) {
					for (int l: forest[k]) {
						for (int m: forest[j]) {
							if (p[m][l] != 0) {
								return 0;
							}
						}
					}
				} else {
					for (int l: forest[k]) {
						for (int m: forest[j]) {
							if (p[m][l] != 2) {
								return 0;
							}
						}
					}
				}
			}
		}
		prev = forest[i][0];
		for (int j: group) {
			ans[prev][forest[j][0]] = 1;
			ans[forest[j][0]][prev] = 1;
			prev = forest[j][0];
		}
		ans[forest[i][0]][forest[i][0]] = 0;
		if (prev ==forest[i][0]) {
			continue;
		}
		ans[prev][forest[i][0]] = 1;
		ans[forest[i][0]][prev] = 1;
	}


	
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for (int i=0;i<forest.size();i++) {
      |               ~^~~~~~~~~~~~~~
supertrees.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for (int j=i+1;j<forest.size();j++) {
      |                  ~^~~~~~~~~~~~~~
supertrees.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |    for (int k=0;k<forest.size();k++) {
      |                 ~^~~~~~~~~~~~~~

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