Submission #1258931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258931		Noname_1900	Connecting Supertrees (IOI20_supertrees)	C++20	21 / 100	118 ms	22132 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
const int NMAX = 1000;
int boss[NMAX];
int findBoss(int noeud)
{
	if(boss[noeud] == noeud)	return noeud;
	return boss[noeud] = findBoss(boss[noeud]);
}
bool merge(int a, int b)
{
	a = findBoss(a);
	b = findBoss(b);
	if(a == b)	return false;
	boss[b] = a;
	return true;
}
vector<vector<int>> answer;
void creer(int a, int b)
{
	a = findBoss(a);
	b = findBoss(b);
	if(a == b) return;
	answer[a][b] = 1;
	answer[b][a] = 1;
	merge(a, b);
}
int construct(vector<vector<int>> p) {
	int n = p.size();
	answer.resize(n, vector<int>(n));
	for(int i = 0; i < n; i++)
	{
		boss[i] = i;
		for(int v = 0; v < n; v++)	answer[i][v] = 0;
	}
	for(int i = 0; i < n; i++)
	{
		for(int autre = 0; autre < i; autre++)
		{
			if(p[i][autre] == 1)
			{
				creer(findBoss(i), findBoss(autre));
			}
		}
	}
	for(int i = 0; i < n; i++)
	{
		for(int autre = 0; autre < i; autre++)
		{
			if(p[i][autre] == 0)
			{
				if(findBoss(i) == findBoss(autre))	return 0;
			}
		}
	}
	build(answer);
	return 1;
}

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