Submission #1253128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253128		jwvg0425	World Map (IOI25_worldmap)	C++20	7 / 100	9 ms	1092 KiB

worldmap

#include "worldmap.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

vector<int> edges[45];
int d[45], h[45], subSz[45];
bool perfect[45];

struct RectBoard
{
	RectBoard(int c, int a, int b) : color(c), width(a), height(b), depth(0), coverC(0) {}

	int color;
	int width, height;
	int depth;
	int coverC = 0;

	~RectBoard()
	{
		for (auto& [k, p] : childs)
			delete p;
	}

	void add_child(int x, int y, RectBoard* r)
	{
		childs.emplace_back(ii(x, y), r);
		depth = max(depth, r->depth + 1);
		if (childs.size() == 1)
			coverC = childs[0].yy->coverC + 1;
	}

	vector<pair<ii, RectBoard*>> childs;

	void paint(vector<vector<int>>& res, int x, int y)
	{
		for (int i = x; i < x + width; i++)
			for (int j = y; j < y + height; j++)
				res[i][j] = color;

		for (auto& [p, c] : childs)
			c->paint(res, x + p.xx, y + p.yy);
	}

	int cover()
	{
		// cover 필요 없는 경우
		if (childs.empty())
			return 0;

		if (childs[0].xx.xx != 0 && childs[0].xx.yy != 0)
			return 0;

		auto csz = childs[0].yy->cover() + 1;
		childs[0].xx.xx += 1;
		childs[0].xx.yy += 1;
		width += csz;
		height += csz;

		for (int i = 1; i < childs.size(); i++)
		{
			childs[i].xx.xx += csz;
			childs[i].xx.yy += csz;
		}

		return csz;
	}

	bool isAdj(ii p)
	{
		for (auto& [cp, v] : childs)
		{
			int lx = cp.xx - 1;
			int rx = cp.xx + v->width;
			int ly = cp.yy - 1;
			int ry = cp.yy + v->height;

			if (p.xx >= lx && p.xx <= rx && p.yy >= ly && p.yy <= ry)
				return true;
		}

		return false;
	}

	vector<ii> getCells()
	{
		vector<ii> res;

		for (int y = height - 2; y >= 0; y -= 1)
		{
			for (int x = y % 2; x < width - 1; x += 2)
			{
				if (isAdj(ii(x, y)))
					continue;

				res.emplace_back(x, y);
			}
		}

		return res;
	}

	void transpose()
	{
		swap(width, height);

		for (auto& [p, c] : childs)
		{
			swap(p.xx, p.yy);
			c->transpose();
		}
	}

	bool overlap(int lx, int ly, int rx, int ry)
	{
		for (auto& [p, c] : childs)
		{
			int lx2 = p.xx - 1;
			int ly2 = p.yy - 1;
			int rx2 = p.xx + c->width;
			int ry2 = p.yy + c->height;

			int minx = max(lx, lx2);
			int maxx = min(rx, rx2);
			int miny = max(ly, ly2);
			int maxy = min(ry, ry2);

			if (minx <= maxx && miny <= maxy)
				return true;
		}

		return false;
	}
};

void predfs(int root)
{
	subSz[root] = 1;
	int backEdge = 0;
	vector<int> cs;
	for (auto& c : edges[root])
	{
		if (d[c] != -1)
		{
			if (d[c] > d[root])
				backEdge++;
			continue;
		}

		cs.push_back(c);
		d[c] = d[root] + 1;
		predfs(c);
		h[root] = max(h[root], h[c] + 1);
		subSz[root] += subSz[c];
	}

	if (cs.empty())
	{
		perfect[root] = true;
	}
	else if (cs.size() == 1 && perfect[cs[0]] && backEdge == subSz[root] - 2)
	{
		perfect[root] = true;
	}
}

RectBoard* dfs(int root, bool maxFirst)
{
	vector<int> backEdges;
	vector<RectBoard*> childBoards;

	if (maxFirst)
		sort(all(edges[root]), [](int l, int r) { return h[r] < h[l]; });
	else
		sort(all(edges[root]), [](int l, int r) { return h[l] < h[r]; });

	int bc = 0;
	for (auto& c : edges[root])
	{
		if (d[c] < d[root])
			continue;

		// back edge 여부 체크
		if (d[c] != d[root] + 1)
		{
			backEdges.push_back(c);
			bc++;
		}
		else
		{
			auto dfsr = dfs(c, maxFirst);
			if (dfsr->width == 1 && dfsr->height == 1)
			{
				backEdges.push_back(dfsr->color);
				delete dfsr;
			}
			else
			{
				childBoards.push_back(dfsr);
			}
			maxFirst = false;
		}
	}

	// leaf node
	if (childBoards.empty() && backEdges.empty())
		return new RectBoard(root, 1, 1);

	// n = 3 완전 그래프  특수 케이스
	if (subSz[root] == 3 && perfect[root])
	{
		auto res = new RectBoard(root, 2, 3);
		res->add_child(0, 0, new RectBoard(childBoards[0]->color, 1, 1));
		res->add_child(0, 1, new RectBoard(childBoards[0]->childs[0].yy->color, 1, 1));
		return res;
	}

	// n = 4 완전 그래프 특수 케이스
	if (subSz[root] == 4 && perfect[root])
	{
		auto res = new RectBoard(root, 3, 4);
		res->add_child(0, 0, childBoards[0]);
		res->childs[0].yy->add_child(1, 1, new RectBoard(root, 1, 1));
		res->childs[0].yy->add_child(1, 2, new RectBoard(res->childs[0].yy->childs[0].yy->color, 1, 1));
		return res;
	}

	for (int i = 1; i < childBoards.size(); i++)
	{
		// 왼쪽 위 감싸기
		childBoards[i]->cover();
	}

	// 자식을 한 칸씩 띄고 배치할 수 있을 만큼으로 크기 지정
	int width = 0;
	int height = 0;

	auto res = new RectBoard(root, width, height);

	for (auto& c : childBoards)
	{
		// width를 확장할지 height를 확장할지 정하기
		vector<tuple<int, int, bool>> candidates;
		for (int x = 0; x <= width; x++)
		{
			for (int y = 0; y <= height; y++)
			{
				if (!res->overlap(x, y, x + c->width - 1, y + c->height - 1))
					candidates.emplace_back(x, y, false);
				
				if (!res->overlap(x - 1, y - 1, x + c->height, y + c->width))
					candidates.emplace_back(x, y, true);
			}
		}

		int x = 0;
		int y = 0;
		bool needTranspose = false;
		int sz = 987654321;

		for (auto& [xi, yi, transpose] : candidates)
		{
			auto wi = transpose ? c->height : c->width;
			auto hi = transpose ? c->width : c->height;
			auto afterw = max(width, xi + wi + 1);
			auto afterh = max(height, yi + hi + 1);

			auto aftersz = max(afterw, afterh);

			if (aftersz < sz)
			{
				sz = aftersz;
				x = xi;
				y = yi;
				needTranspose = transpose;
			}
		}

		if (needTranspose)
			c->transpose();

		res->add_child(x, y, c);

		width = max(width, x + c->width + 1);
		height = max(height, y + c->height + 1);
	}

	res->width = width;
	res->height = height;

	// back edge 칸 계산
	while (true)
	{
		vector<ii> cells = res->getCells();

		if (cells.size() < backEdges.size())
		{
			if (res->width < res->height)
				res->width += 2;
			else
				res->height += 2;
			continue;
		}

		// -1 check
		res->width -= 1;
		vector<ii> wcells = res->getCells();
		res->width += 1;
		res->height -= 1;
		vector<ii> hcells = res->getCells();
		res->height += 1;

		if (wcells.size() >= backEdges.size())
		{
			res->width -= 1;

			for (int i = 0; i < backEdges.size(); i++)
				res->add_child(wcells[i].xx, wcells[i].yy, new RectBoard(backEdges[i], 1, 1));

			break;
		}

		if (hcells.size() >= backEdges.size())
		{
			res->height -= 1;

			for (int i = 0; i < backEdges.size(); i++)
				res->add_child(hcells[i].xx, hcells[i].yy, new RectBoard(backEdges[i], 1, 1));

			break;
		}

		for (int i = 0; i < backEdges.size(); i++)
			res->add_child(cells[i].xx, cells[i].yy, new RectBoard(backEdges[i], 1, 1));

		break;
	}

	return res;
}

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
	for (int i = 1; i <= N; i++)
		edges[i].clear();

	memset(d, -1, sizeof(d));
	memset(h, 0, sizeof(h));
	memset(subSz, 0, sizeof(subSz));
	memset(perfect, false, sizeof(perfect));

	for (int i = 0; i < M; i++)
	{
		edges[A[i]].push_back(B[i]);
		edges[B[i]].push_back(A[i]);
	}

	d[1] = 0;
	predfs(1);
	auto res = dfs(1, true);

	auto sz = max(res->width, res->height);
	res->width = sz;
	res->height = sz;

	vector<vector<int>> ans(sz, vector<int>(sz));
	res->paint(ans, 0, 0);

	delete res;
	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 7 / 7
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 56