제출 #1225829

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225829		Jer	즐거운 행로 (APIO20_fun)	C++20	0 / 100	93 ms	328 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
#include <vector>

using namespace std;
const int MAXN = 505;
vector<int> con[MAXN];
bool used[MAXN];

pair<int, int> find_depth(int curr, int par){ // depth, node
	pair<int, int> res = {-1, -1};

	for (auto i : con[curr]){
		if (i == par or used[i]) continue;

		pair<int, int> b = find_depth(i, curr);
		if (b.first > res.first) res = b;
	}

	if (res.first == -1)
		return {1, curr};
	return {res.first + 1, res.second};
}

pair<int, int> find_remove(int start){ // node1, node2
	pair<int, int> b1 = {-1, -1}, b2 = {-1, -1};

	for (auto i : con[start]){
		if (used[i]) continue;

		pair<int, int> res = find_depth(i, start);

		if (b1.first == -1) b1 = res;
		else if (b2.first == -1 and b2.second != res.second and b1.second != res.second) b2 = res;
		else if (res.first > b1.first and b2.second != res.second and b1.second != res.second) b2 = b1, b1 = res;
		else if (res.first > b2.first and b2.second != res.second and b1.second != res.second) b2 = res;
	}

	if (b2.second == -1)
		b2.second = start;

	return {b1.second, b2.second};
}

void make_tree(int n){
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (hoursRequired(i, j) == 1)
				con[i].push_back(j), con[j].push_back(i);
}

std::vector<int> createFunTour(int n, int Q) {
  	vector<int> res;

	make_tree(n);

	int total = n, prev = -1;
	while (total > 2){
		int start;

		for (int i = 0; i < n; i++)
			if (!used[i]) {start = i; break;}
		
		pair<int, int> t = find_remove(start);
		total--;
		if (prev == -1)
		{
			prev = t.second;
			used[t.first] = true;
			res.push_back(t.first);
		}
		else
		{
			res.push_back(prev);
			used[prev] = true;
			prev = (t.first != prev) ? t.first : t.second;
		}
	}

	for (int i = 0; i < n; i++)
		if (!used[i]) res.push_back(i);

	return res;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34