Submission #302759

#	Time	Username	Problem	Language	Result	Execution time	Memory
302759		kimjg1119	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	275 ms	22268 KiB

supertrees

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

int pa[1010];

int fi(int x) {
	return pa[x] = x == pa[x] ? x : fi(pa[x]);
}
void un(int a, int b) {
	a = fi(a); b = fi(b);
	if (a == b) return;
	pa[a] = b;
}

vector<int> v[1010];
int cyc[1010], cnt = 0;

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> ans;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		ans.push_back(row);
	}
	for (int i = 0; i < n; i++) pa[i] = i;

	//start here

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			if (p[i][j]) un(i, j);
			if (p[i][j] == 3) return 0;
		}
			

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if ((bool)p[i][j] != (fi(i) == fi(j))) return 0;
		}
	}
	for (int i = 0; i < n; i++)
		v[fi(i)].push_back(i);

	// finished component distribute

	for (int k = 0; k < n; k++) {
		if (v[k].size() <= 1) continue;
		if (v[k].size() == 2) {
			if (p[v[k][0]][v[k][1]] == 2) return 0;
			else {
				ans[v[k][0]][v[k][1]] = ans[v[k][1]][v[k][0]] = 1;
				continue;
			}
		}

		int m = v[k].size(), flag = 1;

		//check all 1
		for (int i = 0; i < m; i++)
			for (int j = 0; j < m; j++)
				if (p[v[k][i]][v[k][j]] == 2) flag = 0;
		if (flag) {
			for (int i = 0; i < m - 1; i++) {
				int a = v[k][i], b = v[k][i + 1];
				ans[a][b] = ans[b][a] = 1;
			}
			continue;
		}

		// union all 1 and check
		for (int i = 0; i < n; i++) pa[i] = i;
		for (int i = 0; i < m; i++)
			for (int j = i + 1; j < m; j++)
				if (p[v[k][i]][v[k][j]] == 1) un(v[k][i], v[k][j]);
		for (int i = 0; i < m; i++)
			for (int j = i + 1; j < m; j++)
				if (p[v[k][i]][v[k][j]] == 2 && fi(v[k][i]) == fi(v[k][j])) return 0;

		// remain edges
		vector<vector<int>> ad(n);
		vector<int> chk(n);
		vector<int> root;

		for (int i = 0; i < m; i++)
			ad[fi(v[k][i])].push_back(v[k][i]);
		for (int i = 0; i < n; i++) {
			if (ad[i].empty()) continue;
			root.push_back(ad[i][0]);
			for (int j = 0; j + 1 < ad[i].size(); j++) {
				int a = ad[i][j], b = ad[i][j + 1];
				ans[a][b] = ans[b][a] = 1;
			}
		}
		if (root.size() <= 2) return 0;

		// make cycle
		for (int i = 0; i < root.size(); i++) {
			int a = root[i], b = root[(i + 1) % root.size()];
			ans[a][b] = ans[b][a] = 1;
		}
	}

	build(ans);
	return 1;
}

Compilation message (stderr)

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

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