Submission #423173

#	Time	Username	Problem	Language	Result	Execution time	Memory
423173		JUANDI321	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	0 ms	204 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <deque>
 
using namespace std;
bool ch[1010];
 
int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> answer;
	for (int i = 0; i < n; i++) 
	{
		vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	for(int i = 0; i<n; i++)
	{
		for(int j = i+1; j<n; j++)
		{
			if(p[i][j] == 0)
			{
				for(int h = 0; h < n; h++)
				{
					if(p[i][h] == 1 && p[j][h] == 1)return 0;
				}
			}
		}
	}
	deque<int> l;
	for(int i = 0; i<n; i++)
	{
		if(!ch[i])
		{
			ch[i]=true;
			l.clear();
			l.push_back(i);
			int ant = i;
			int c = 1;
			for(int j = 0; j<n; j++)
			{
				if(p[i][j] == 1 && i != j)
				{
					ch[j]=true;
					answer[ant][j]=1;
					answer[j][ant]=1;
					ant = j;
					l.push_back(j);
					c++;
				}
			}
			if(c>=2)
			{
				answer[l.front()][l.back()] = 1;
				answer[l.back()][l.front()] = 1;
			}
			else return 0;
		}
	}
	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