Submission #423288

#	Time	Username	Problem	Language	Result	Execution time	Memory
423288		JUANDI321	Connecting Supertrees (IOI20_supertrees)	C++17	11 / 100	1077 ms	23432 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <deque>
#include <iostream>

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] == 2 && p[j][h] == 2)return 0;
					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 ant1 = i, ant2 = i;
			int c = 1;
			for(int j = 0; j<n; j++)
			{
				if(p[i][j] == 2 && i != j)
				{
					ch[j]=true;
					answer[ant1][j]=1;
					answer[j][ant1]=1;
					ant1 = j;
					l.push_back(j);
					c++;
				}
				if(p[i][j] == 1 && i != j)
				{
					ch[j]=true;
					answer[ant2][j]=1;
					answer[j][ant2]=1;
					ant2 = j;
				}
			}
			if(c>2)
			{
				answer[l.front()][l.back()] = 1;
				answer[l.back()][l.front()] = 1;
			}
			else if(c!=1)return 0;
		}
	}
	build(answer);
	return 1;
}

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