제출 #1238489

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238489		CyberCow	가장 긴 여행 (IOI23_longesttrip)	C++20	0 / 100	168 ms	408 KiB

longesttrip

#include "longesttrip.h"
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

const int n = 250;
int st[n][n];

vector<int> longest_trip(int N, int D)
{
	vector<int> ans;
	for (int i = 0; i < N; i++)
	{
		for (int j = i + 1; j < N; j++)
		{
			if (are_connected({ i }, { j }))
			{
				st[i][j] = 1;
				st[j][i] = 1;
			}
		}
	}
	vector<int> a = { 0 }, b = { 1 };
	for (int i = 2; i < N; i++)
	{
		if (st[a.back()][i])
		{
			a.push_back(i);
		}
		else if (st[b.back()][i])
		{
			b.push_back(i);
		}
		else
		{
			for (int j = b.size() - 1; j >= 0; j--)
			{
				a.push_back(b[j]);
			}
			b.clear();
			b.push_back(i);
		}
	}
	vector<vector<int>> qaq;
	if (a.size() < b.size())swap(a, b);
	qaq.push_back(a);
	qaq.push_back(b);
	int arec = 1;
	for (int x = 0; x < qaq[0].size(); x++)
	{
		int kanckacnem = 0;
		for (int y = 0; y < qaq[1].size(); y++)
		{
			int a1 = x + 1, a2 = qaq[0].size() - x;
			int b1 = y + 1, b2 = qaq[1].size() - y;
			int maxerk = max(max(a1 + b1, a1 + b2), max(a2 + b1, a2 + b2));
			kanckacnem = max(kanckacnem, maxerk);
		}
		if (kanckacnem > qaq[0].size())
		{
			for (int y = 0; y < qaq[1].size(); y++)
			{
				if (st[qaq[0][x]][qaq[1][y]] != 1)continue;
				int a1 = x + 1, a2 = qaq[0].size() - x;
				int b1 = y + 1, b2 = qaq[1].size() - y;
				int maxerk = max(max(a1 + b1, a1 + b2), max(a2 + b1, a2 + b2));
				if (maxerk == kanckacnem)
				{
					if (a1 + b1 == maxerk)
					{
						while (qaq[0].size() > a1)
						{
							qaq[0].pop_back();
						}
						while (qaq[1].size() > b1)
						{
							qaq[1].pop_back();
						}
						while (!qaq[1].empty())
						{
							qaq[0].push_back(qaq[1].back());
							qaq[1].pop_back();
						}
					}
					else if (a1 + b2 == maxerk)
					{
						while (qaq[0].size() > a1)
						{
							qaq[0].pop_back();
						}
						reverse(qaq[1].begin(), qaq[1].end());
						while (qaq[1].size() > b2)
						{
							qaq[1].pop_back();
						}
						while (!qaq[1].empty())
						{
							qaq[0].push_back(qaq[1].back());
							qaq[1].pop_back();
						}
					}
					else if (a2 + b1 == maxerk)
					{
						reverse(qaq[0].begin(), qaq[0].end());
						while (qaq[0].size() > a2)
						{
							qaq[0].pop_back();
						}
						while (qaq[1].size() > b1)
						{
							qaq[1].pop_back();
						}
						while (!qaq[1].empty())
						{
							qaq[0].push_back(qaq[1].back());
							qaq[1].pop_back();
						}
					}
					else
					{
						reverse(qaq[0].begin(), qaq[0].end());
						while (qaq[0].size() > a2)
						{
							qaq[0].pop_back();
						}
						reverse(qaq[1].begin(), qaq[1].end());
						while (qaq[1].size() > b2)
						{
							qaq[1].pop_back();
						}
						while (!qaq[1].empty())
						{
							qaq[0].push_back(qaq[1].back());
							qaq[1].pop_back();
						}
					}
				}
			}
		}
	}
	return qaq[0];
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60