Submission #1264568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264568		Noname_1900	Connecting Supertrees (IOI20_supertrees)	C++20	56 / 100	160 ms	28512 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
const int NMAX = 1000;
int boss[4][NMAX];
set<int> dansComp[4][NMAX];
vector<int> chemins[4][NMAX];
int findBoss(int noeud, int iType)
{
	if(boss[iType][noeud] == noeud)	return noeud;
	return boss[iType][noeud] = findBoss(boss[iType][noeud], iType);
}
int _size[4][NMAX];
bool merge(int a, int b, int iType)
{
	a = findBoss(a, iType);
	b = findBoss(b, iType);
	if(a == b)	return false;
	if(_size[iType][b] > _size[iType][a])
	{
		swap(a, b);
	}
	_size[iType][a] += _size[iType][b];
	boss[iType][b] = a;
	for(int i : dansComp[iType][b])	dansComp[iType][a].insert(i);
	dansComp[iType][b].clear();
	return true;
}
vector<vector<int>> answer;
void creer(int a, int b, int iType)
{
	answer[a][b] = 1;
	answer[b][a] = 1;
	merge(a, b, iType);
}
/*
bool dansCycle[NMAX];

void parcours(int noeud)
{
	for(int pro : chemins[1][noeud])
	{
		if(findBoss(pro) == findBoss(noeud))	continue;
		creer(noeud, pro);
		parcours(pro);
	}
}/** */
int vu[NMAX];
int construct(vector<vector<int>> p) {
	int n = p.size();
	answer.resize(n, vector<int>(n));
	for(int i = 0; i < n; i++)
	{
		for(int n = 0; n < 4; n++)
		{
			_size[n][i] = 1;
			boss[n][i] = i;
			dansComp[n][i].insert(i);
		}
		
		for(int v = 0; v < n; v++)	answer[i][v] = 0;
	}
	for(int i = 0; i < n; i++)
	{
		for(int c = 0; c < n ; c ++)
		{
			if(i == c)	continue;
			int type = p[i][c];
			chemins[type][i].push_back(c);
		}
	}
	/*
	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;
			}
		}
	}
		/** */
	//type1
	for(int i = 0; i < n; i++)
	{
		for(int autre = 0; autre < n; autre++)
		{
			if(p[i][autre] != p[autre][i])	return 0;
			if(i == autre)	continue;
			if(p[i][autre] == 1)
			{
				merge(findBoss(i, 1), findBoss(autre, 1), 1);
			}
		}
	}
	for(int noeud1 = 0; noeud1 < n; noeud1++)
	{
		if(findBoss(noeud1, 1) != noeud1)	continue;
		if(dansComp[1][noeud1].size() == 1)	continue;
		for(int autre : dansComp[1][noeud1])
		{
			if(autre == noeud1)	continue;
			creer(noeud1, autre, 1);
		}
	}
	for(int i = 0; i < n; i++)
	{
		for(int autre = 0; autre < n; autre++)
		{
			if(i == autre)	continue;
			if((findBoss(i, 1) == findBoss(autre, 1)) && (p[i][autre] != 1))	return 0;//Averifier
		}
	}
	//type2
	for(int i = 0; i < n; i++)
	{
		for(int autre = 0; autre < n; autre++)
		{
			if(i == autre)	continue;
			if(p[i][autre] == 2)
			{
				merge(findBoss(i, 2), findBoss(autre, 2), 2);
			}
		}
	}

	for(int noeud2 = 0; noeud2 < n; noeud2++)
	{
		if(findBoss(noeud2, 2) != noeud2)	continue;
		if(dansComp[2][noeud2].size() == 1)	continue;
		if(dansComp[2][noeud2].size() == 2)	return 0;
		int b = *dansComp[2][noeud2].rbegin();
		b = findBoss(b, 1);
		for(int autre : dansComp[1][b])	
		{
			if(!dansComp[2][noeud2].count(autre))	return 0;
		}
		vu[b] = 2;
		int nbApp = 0;
		int iEme = -1;
		for(int a : dansComp[2][noeud2])
		{
			iEme++;
			a= findBoss(a, 1);
			if((vu[a] == 2) && (iEme != dansComp[2][noeud2].size()-1))
				continue;
			vu[a] = 2;
			nbApp++;
			creer(a, b, 2);
			b = a;
		}
		if(nbApp < 2)	return 0;
	}
	/*
	for(int i = 0; i < n; i++)
	{
		for(int autre = 0; autre < n; autre++)
		{
			if(i == autre)	continue;
			if((findBoss(i, 2) != findBoss(autre, 2)) && (p[i][autre] == 2))	return 0;
		}
	}
		/** */
//	cout << "passe" << endl;
/**
	for(int i = 0; i < n; i++)
	{
		for(int autre = 0; autre < n; autre++)
		{
			//cout << i << " " << autre << endl;
			if(i == autre)	continue;
			if(p[i][autre] == 0)
			{
				if(findBoss(i) == findBoss(autre))	return 0;
			}
		}
	}
	//cout << "passe" << endl;
	/** */
	/*
	// cycle de 2
	for(int i = 0; i < n; i++)
	{
		if(findBoss(i) == i)
		{
			if(dansComp[i].size() == 1) continue;
			//if(dansComp[i].size() == 2)	return 0;
		//	cout << endl;
			for(int iDansComp=0; iDansComp < dansComp[i].size(); iDansComp++)
			{
				//cout << dansComp[i][iDansComp] << " ";
				int b;
				if(iDansComp == 0)
				{
					b = dansComp[i][dansComp[i].size()-1];
				}
				else
					b = dansComp[i][iDansComp-1];
				int a = dansComp[i][iDansComp];
				dansCycle[a] = true;
				creer(a, b);
			}
		}
	}
	// parcours pour arbre depuis cycle
	for(int i = 0; i < n; i++)
	{
		if(!dansCycle[i])	continue;
		parcours(i);
	}
	//reste
	for(int i = 0; i < n; i++)	parcours(i);
	for(int i = 0; i < n; i++)
	{
		for(int autre = 0; autre < n; autre++)
		{
			if(i == autre)	continue;
			if(((p[i][autre] == 0) && (findBoss(i) == findBoss(autre))) || ((p[i][autre] > 0) && (findBoss(i) != findBoss(autre))))	return 0;
		}
	}
		/** */
	build(answer);
	return 1;
}

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