제출 #1225975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225975		Jer	즐거운 행로 (APIO20_fun)	C++20	0 / 100	0 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};
}

int find_remove(int start){ // node
	pair<int, int> best ={-1, -1};
	for (auto i : con[start]){
		if (used[i]) continue;

		pair<int, int> res = find_depth(i, start);
		if (best.second == -1 or (best.second != res.second and best.first < res.first))
			best = res;
	}

	return best.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);

	for (int start = 0; start < n; start++){
		int total = n;
		for (int i = 0; i < n; i++) used[i] = false;
		res.clear();

		while (total > 1){
			if (used[start])
				break;
			
			int t = find_remove(start);
			total--;
			used[t] = true;
			res.push_back(t);
		}

		if (!used[start]) break;
	}

	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