Submission #1264003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264003		Noname_1900	Connecting Supertrees (IOI20_supertrees)	C++20	21 / 100	128 ms	28416 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
const int NMAX = 1000;
int boss[NMAX];
vector<int> dansComp[NMAX];
vector<int> chemins[3][NMAX];
int findBoss(int noeud)
{
	if(boss[noeud] == noeud)	return noeud;
	return boss[noeud] = findBoss(boss[noeud]);
}
int _size[NMAX];
bool merge(int a, int b)
{
	a = findBoss(a);
	b = findBoss(b);
	if(a == b)	return false;
	if(_size[b] > _size[a])
	{
		swap(a, b);
	}
	_size[a] += _size[b];
	boss[b] = a;
	for(int i : dansComp[b])	dansComp[a].push_back(i);
	return true;
}
vector<vector<int>> answer;
void creer(int a, int b)
{
	
	answer[a][b] = 1;
	answer[b][a] = 1;
	merge(a, b);
}
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 construct(vector<vector<int>> p) {
	int n = p.size();
	answer.resize(n, vector<int>(n));
	for(int i = 0; i < n; i++)
	{
		_size[i] = 1;
		boss[i] = i;
		dansComp[i].push_back(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 ++)
		{
			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;
			}
		}
	}
		/** */
	for(int i = 0; i < n; i++)
	{
		for(int autre = 0; autre < n; autre++)
		{
			if(p[i][autre] == 2)
			{
				merge(findBoss(i), findBoss(autre));
			}
		}
	}
//	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(((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: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4