Submission #580369

#	Time	Username	Problem	Language	Result	Execution time	Memory
580369		joelau	Connecting Supertrees (IOI20_supertrees)	C++14	96 / 100	238 ms	24088 KiB

supertrees

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

int N,ufds[1005], rnk[1005], ufds2[1005], rnk2[1005];
vector<int> lst[1005];

int findSet(int i) {
	return ufds[i] == i ? i : ufds[i] = findSet(ufds[i]);
}

void unionSet(int i, int j) {
	int a = findSet(i), b = findSet(j);
	if (a == b) return;
	if (rnk[a] < rnk[b]) ufds[a] = b;
	if (rnk[a] > rnk[b]) ufds[b] = a;
	if (rnk[a] == rnk[b]) ufds[a] = b, rnk[b]++;
}

int findSet2(int i) {
	return ufds2[i] == i ? i : ufds2[i] = findSet2(ufds2[i]);
}

void unionSet2(int i, int j) {
	int a = findSet2(i), b = findSet2(j);
	if (a == b) return;
	if (rnk2[a] < rnk2[b]) ufds2[a] = b;
	if (rnk2[a] > rnk2[b]) ufds2[b] = a;
	if (rnk2[a] == rnk2[b]) ufds2[a] = b, rnk2[b]++;
}

int construct(vector<vector<int>> p) {
	N = p.size();
	for (int i = 0; i < N; ++i) ufds[i] = i, rnk[i] = 1, ufds2[i] = i, rnk2[i] = 1;
	for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) if (p[i][j] == 1) unionSet(i,j);
	for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) if (p[i][j] == 0 && findSet(i) == findSet(j)) return 0;
	vector< vector<int> > ans (N, vector<int>(N,0));
	for (int i = 0; i < N; ++i) if (findSet(i) != i) ans[i][findSet(i)] = ans[findSet(i)][i] = 1;
	for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) if (p[i][j] == 2) unionSet2(findSet(i),findSet(j));
	for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) if (p[i][j] == 0 && findSet2(findSet(i)) == findSet2(findSet(j))) return 0;
	for (int i = 0; i < N; ++i) if (findSet(i) == i) lst[findSet2(i)].push_back(i);
	for (int i = 0; i < N; ++i) {
		if (lst[i].size() == 2) return 0;
		if (lst[i].size() >= 3) {
			for (int j = 1; j < lst[i].size(); ++j) ans[lst[i][j-1]][lst[i][j]] = ans[lst[i][j]][lst[i][j-1]] = 1;
			ans[lst[i].front()][lst[i].back()] = ans[lst[i].back()][lst[i].front()] = 1;
		}
	}
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    for (int j = 1; j < lst[i].size(); ++j) ans[lst[i][j-1]][lst[i][j]] = ans[lst[i][j]][lst[i][j-1]] = 1;
      |                    ~~^~~~~~~~~~~~~~~

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