Submission #1251605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251605		jwvg0425	World Map (IOI25_worldmap)	C++20	72 / 100	46 ms	5700 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 h[45];

struct RectBoard
{
	RectBoard(int c, int s) : color(c), sz(s), depth(0), coverC(0) {}

	int color;
	int sz;
	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);
	}

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

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

		for (auto& [p, c] : childs)
			c->paint(res, x + p.xx, y + p.yy);
	}
	
	void arrange()
	{
		int minCoverC = 0;
		int idx = 0;

		for (int i = 0; i < childs.size(); i++)
		{
			if (childs[i].yy->coverC < minCoverC)
			{
				minCoverC = childs[i].yy->coverC;
				idx = i;
			}
		}

		swap(childs[0], childs[idx]);

		int x = 0, y = 0;
		for (int i = 0; i < childs.size(); i++)
		{
			childs[i].xx.xx = x;
			childs[i].xx.yy = y;
			x += childs[i].yy->sz + 1;
		}

		coverC = minCoverC + 1;
	}

	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;
		sz += csz;

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

		return csz;
	}
};

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

	for (auto& c : edges[root])
	{
		if (h[c] != -1)
		{
			// back edge 여부 체크
			if (h[c] > h[root])
				backEdges.push_back(c);
		}
		else
		{
			h[c] = h[root] + 1;
			childBoards.push_back(dfs(c));
		}
	}

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

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

	// 자식을 한 칸씩 띄고 배치할 수 있을 만큼으로 크기 지정
	int childSz = childBoards.size();
	int childMax = 0;
	for (auto& c : childBoards)
	{
		childSz += c->sz;
		childMax = max(childMax, c->sz);
	}

	int backEdgeSz = backEdges.size() * 2;
	if (!backEdges.empty())
		childMax += 3;

	auto sz = max({ backEdgeSz, childSz, childMax });

	auto res = new RectBoard(root, sz);
	int x = 0, y = 0;

	for (auto& c : childBoards)
	{
		res->add_child(x, y, c);
		x += c->sz + 1;
	}

	res->arrange();

	x = 0;
	y = sz - 2;
	for (auto& b : backEdges)
	{
		res->add_child(x, y, new RectBoard(b, 1));
		x += 2;
	}

	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(h, -1, sizeof(h));

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

	h[1] = 0;
	auto res = dfs(1);

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

	delete res;
	return ans;
}

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