Submission #1258934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258934		Noname_1900	Connecting Supertrees (IOI20_supertrees)	C++20	0 / 100	0 ms	328 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
const int NMAX = 1000;
int boss[NMAX];
vector<int> dansComp[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;
	for(int i : dansComp[b])	dansComp[a].push_back(b);
	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;
			}
		}
	}
		/** */
	for(int i = 0; i < n; i++)
	{
		for(int autre = 0; autre < i; autre++)
		{
			if(p[i][autre] == 2)
			{
				merge(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;
			}
		}
	}
	for(int i = 0; i < n; i++)
	{
		if(findBoss(i) == i)
		{
			if(dansComp[i].size() == 1) continue;
			for(int iDansComp=0; iDansComp < dansComp[i].size(); iDansComp++)
			{
				int b;
				if(iDansComp == 0)
				{
					b = dansComp[i][dansComp[i].size()-1];
				}
				else
					b = dansComp[i][iDansComp-1];
				int a = dansComp[i][iDansComp];
				answer[a][b] = 1;
				answer[b][a] = 1;
			}
		}
	}
	build(answer);
	return 1;
}

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