Submission #302971

#	Time	Username	Problem	Language	Result	Execution time	Memory
302971		8e7	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	257 ms	22392 KiB

supertrees

//Challenge: Accepted
#include "supertrees.h"
#include <vector>
#include <iostream>
#include <set>
#define maxn 1005
using namespace std;
int par[maxn], link[maxn];
vector<int> group[maxn], lg[maxn];
int getpar(int a, int x[]) {
	return a == x[a] ? a : x[a] = getpar(x[a], x);
}
void combine(int a, int b, int x[]) {
	x[getpar(a, x)] = getpar(b, x);
}
int construct(vector<vector<int> > p) {
	int n = p.size();
	int type = 2;
	for (int i = 0;i < n;i++) par[i] = i, link[i] = i;
	for (int i = 0;i < n;i++) {
		for (int j = i + 1;j < n;j++) {
			if (p[i][j]) {
				if (p[i][j] == 1) type = 1;
				if (p[i][j] == 3) return 0;
				combine(i, j, par);
			}
		}
	}
	for (int i = 0;i < n;i++) {
		par[i] = getpar(i, par);
		group[par[i]].push_back(i);
	}
	vector<vector<int> > ans;
	for (int i = 0;i < n;i++) {
		vector<int> add(n, 0);
		ans.push_back(add);
	}
	for (int i = 0;i < n;i++) {
		int x = group[i].size();
		set<int> cycle;
		vector<int> cs;
		for (int j = 0;j < x;j++) {
			for (int k = j + 1;k < x;k++) {
				if (p[group[i][j]][group[i][k]] == 0) {
					return 0;
				}
				if (p[group[i][j]][group[i][k]] == 1) {
					combine(group[i][j], group[i][k], link);
				}
			}
			if (type == 2 && x > 1) {
				if (j) {
					ans[group[i][j - 1]][group[i][j]] = ans[group[i][j]][group[i][j - 1]] = 1;
				}
				ans[group[i][0]][group[i][x - 1]] = ans[group[i][x - 1]][group[i][0]] = 1;
				if (x == 2){
					return 0;
				}
			}
		}
		if (type != 2) {
			for (int j = 0;j < x;j++) {
				getpar(group[i][j], link);
				cycle.insert(link[group[i][j]]);
				lg[link[group[i][j]]].push_back(group[i][j]);
			}
			for (int j:cycle) {
				cs.push_back(j);
				for (int k = 0;k < lg[j].size();k++) {
					for (int l = k + 1;l < lg[j].size();l++) {
						if (p[lg[j][k]][lg[j][l]] != 1) {
							return 0;
						}
					}
				}
			}
			for (int j = 0;j < x;j++) {
				if (link[group[i][j]] != group[i][j]) {
					ans[group[i][j]][link[group[i][j]]] = ans[link[group[i][j]]][group[i][j]] = 1;
				}
			}
			if (cs.size() > 1) {
				if (cs.size() == 2){
					return 0;
				}
				for (int j = 0;j < cs.size();j++) {
					int pre = (j - 1 + cs.size()) % cs.size();
					ans[cs[j]][cs[pre]] = ans[cs[pre]][cs[j]] = 1;
				}
			}
		}
	}
	build(ans);
	return 1;
}
/*
6
1 2 2 2 0 0
2 1 2 2 0 0
2 2 1 1 0 0
2 2 1 1 0 0
0 0 0 0 1 1
0 0 0 0 1 1

6
1 2 2 1 2 1
2 1 2 2 1 2
2 2 1 2 2 1
1 2 2 1 2 2
2 1 2 2 1 2
1 2 1 2 2 1

4
1 2 2 0
2 1 2 0
2 2 1 0
0 0 0 1

4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
 */

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int k = 0;k < lg[j].size();k++) {
      |                    ~~^~~~~~~~~~~~~~
supertrees.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |      for (int l = k + 1;l < lg[j].size();l++) {
      |                         ~~^~~~~~~~~~~~~~
supertrees.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for (int j = 0;j < cs.size();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