Submission #303007

#	Time	Username	Problem	Language	Result	Execution time	Memory
303007		tutis	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	256 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int construct(vector<vector<int>> p) {
	int n = p.size();
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (p[i][j] == 3)
				return 0;
	int C[n];
	iota(C, C + n, 0);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			if (p[i][j] == 1 && C[i] != C[j])
			{
				int x = C[i];
				for (int a = 0; a < n; a++)
					if (C[a] == x)
						C[a] = C[j];
			}
		}
	vector<vector<int>>ans(n, vector<int>(n, 0));
	for (int i = 0; i < n; i++)
		if (C[i] != i)
			ans[i][C[i]] = ans[C[i]][i] = 1;
	int X[n];
	for (int i = 0; i < n; i++)
		if (C[i] == i)
			X[i] = i;
		else
			X[i] = -1;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			if (p[i][j] == 2 && X[i] != X[j] && X[i] != -1 && X[j] != -1)
			{
				int x = X[i];
				for (int a = 0; a < n; a++)
					if (X[a] == x)
						X[a] = X[j];
			}
		}
	for (int i = 0; i < n; i++)
	{
		vector<int>x;
		for (int j = 0; j < n; j++)
			if (X[j] == i)
				x.push_back(j);
		if (x.size() > 1)
		{
			if (x.size() == 2)
				return 0;
			int a = x.back();
			for (int b : x)
			{
				ans[a][b] = ans[b][a] = 1;
				a = b;
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (p[i][j] == 0 && X[C[i]] == X[C[j]])
				return 0;
			if (p[i][j] == 1 && C[i] != C[j])
				return 0;
			if (p[i][j] == 2 && X[C[i]] != X[C[j]] || C[i] == C[j])
				return 0;
		}
	}
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:70:21: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   70 |    if (p[i][j] == 2 && X[C[i]] != X[C[j]] || C[i] == C[j])

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