제출 #795157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
795157		adrilen	슈퍼트리 잇기 (IOI20_supertrees)	C++17	96 / 100	189 ms	27260 KiB

supertrees

#include "supertrees.h"
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using arr = array<int, 2>;
using arrr = array<int, 3>;

constexpr int maxn = 1e3 + 5;

int next_group = 1;
int groups[maxn] = { 0 }, gnode[maxn] = { 0 }, siz[maxn] = { 0 };
bool done[maxn] = { 0 };

vector <int> adj[maxn];


int construct(std::vector<std::vector<int>> p) {

	int g;
	int n = p.size();

	vector<vector<int>> output(n, vector<int>(n));


	for (int i = 0; i < n; i++)
	{
		if (groups[i]) continue;

		g = next_group++;

		vector<int> clique = { i };

		for (int y = i + 1; y < n; y++)
		{
			if (p[i][y] == 1) clique.emplace_back(y);
		}
		gnode[g] = i;

		for (int y : clique) {
			groups[y] = g;

			if (p[y] != p[gnode[g]]) goto impossible;
		}

		for (int i = 1; i < (int)clique.size(); i++)
		{
			output[clique[i]][clique[i - 1]] = output[clique[i - 1]][clique[i]] = 1;
		}

		siz[g] = clique.size();

		set <int> seen;
		for (int y = 0; y < i; y++)
		{
			if (p[i][y] != 0 && seen.count(groups[y]) == 0) {
				adj[g].push_back(groups[y]);
				seen.insert(groups[y]);
				adj[groups[y]].push_back(g);
			}
		}
	}

	// cerr << "Groups complete\n";

	// Combining groups
	// in each connected component, there must be either 2, 3, or none, but not both

	for (int i = 1; i < next_group; i++)
	{
		if (done[i]) continue;

		vector<int> gs = adj[i];
		gs.insert(gs.begin(), i);

		vector<int> twos, threes, ones;

		if (gs.size() == 1) continue;
		// cout << i << "\n";
		// for (int y : gs) cout << y << " ";
		// cout << "\n";

		for (int x : gs)
		{
			vector<int> test = adj[x];

			test.insert(lower_bound(test.begin(), test.end(), x), x);
			// for (int y : test) cout << y << " ";
			// cout << "\n";


			if (test != gs) goto impossible;

			done[x] = true;
			int one = 0;
			bool two, three;
			two = three = false;

			for (int y : p[gnode[x]])
			{
				if (y == 1) one ++;
				else if (y == 2) two = true;
				else if (y == 3) three = true;
			}
			
			if (two && three) goto impossible;
			
			if (one > 1) ones.emplace_back(x); 
			else if (two) twos.emplace_back(x);
			else if (three) threes.emplace_back(x);
		}

		// cout << "Counting finished\n";

		// cerr << ones.size() << " " << twos.size() << " " << threes.size() << " \n";

		if (threes.empty())
		{
			// Twos

			if (gs.size() == 2) goto impossible;

			// Make a cycle
			for (int y = 0; y < (int)gs.size() - 1; y++)
			{
				output[gnode[gs[y]]][gnode[gs[y + 1]]] = output[gnode[gs[y + 1]]][gnode[gs[y]]] = 1;
			}
			output[gnode[gs[0]]][gnode[gs[gs.size() - 1]]] = output[gnode[gs[gs.size() - 1]]][gnode[gs[0]]] = 1;

			
		}
	}


	
	// Build
	build(output);
	return 1;


	impossible:

	return 0;
}

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