제출 #1166753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166753		MateiKing80	슈퍼트리 잇기 (IOI20_supertrees)	C++20	100 / 100	123 ms	22216 KiB

supertrees

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

using namespace std;

int papa[1010];
vector<int> fii[1010];

int realPapa(int x) 
{
	return x == papa[x] ? x : papa[x] = realPapa(papa[x]); 
}

void join(int x, int y) 
{ 
	papa[realPapa(x)] = realPapa(y); 
}

int construct(vector<vector<int>> p)
{
	int n = p.size();
	vector<vector<int>> ret(n, vector<int>(n));

	for(int i = 0; i < n; i ++) 
		papa[i] = i;
	for(int i = 0; i < n; i ++)
	{
		for(int j = 0; j < n; j ++)
		{
			if(p[i][j] == 3) 
				return 0;
			if(p[i][j]) 
				join(i, j);
		}
	}
	for(int i = 0; i < n; i ++) 
		fii[realPapa(i)].push_back(i);

	for(int i = 0; i < n; i ++) 
		if(fii[i].size())
		{
			vector<int> tmp = fii[i];
			for(int j : tmp) 
				for(int k : tmp) 
					if(p[j][k] == 0) 
						return 0;
			for(int j : tmp) 
				papa[j] = j, fii[j].clear();
			for(int j : tmp) 
				for(int k : tmp) 
					if(p[j][k] == 1) join(j, k);
			for(int j : tmp) 
				fii[realPapa(j)].push_back(j);

			vector<int> head;
			for(int j : tmp) 
				if(fii[j].size())
				{
					head.push_back(j);
					for(int k : fii[j]) 
						for(int l : fii[j]) 
							if(p[k][l] == 2) 
								return 0;
					for(int k = 0; k < (int)fii[j].size() - 1; k ++) 
						ret[fii[j][k]][fii[j][k + 1]] = ret[fii[j][k + 1]][fii[j][k]] = 1;
				}
			if(head.size() == 2) 
				return 0;
			if(head.size() >= 3)
			{
				for(int j = 0; j < (int)head.size() - 1; j ++) 
					ret[head[j]][head[j + 1]] = ret[head[j + 1]][head[j]] = 1;
				ret[head.back()][head[0]] = ret[head[0]][head.back()] = 1;
			}
		}
	build(ret);
	return 1;
}

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