제출 #841029

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
841029		jhwest2	가장 긴 여행 (IOI23_longesttrip)	C++17	15 / 100	17 ms	336 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;

pair<int, int> find_edge(vector<int> p1, vector<int> p2) {
	if (p1.size() == 1 && p2.size() == 1) {
		return {p1[0], p2[0]};
	}
	if (p1.size() == 1) {
		int m = (int)p2.size() / 2;
		vector<int> left = vector<int>(p2.begin(), p2.begin() + m);
		vector<int> right = vector<int>(p2.begin() + m, p2.end());
		if (are_connected(p1, left)) 
			return find_edge(p1, left);
		else 
			return find_edge(p1, right);
	}
	else {
		int m = (int)p1.size() / 2;
		vector<int> left = vector<int>(p1.begin(), p1.begin() + m);
		vector<int> right = vector<int>(p1.begin() + m, p1.end());
		if (are_connected(left, p2))
			return find_edge(left, p2);
		else
			return find_edge(right, p2);
	}
}
vector<int> longest_trip(int N, int D)
{
	if (D == 3) {
		vector<int> res(N);
		iota(res.begin(), res.end(), 0);
		return res;
	}
	if (D == 2) {
		deque<int> dq = {0};
		vector<bool> chk(N);
		for (int i = 1; i < N; i++) {
			if (are_connected({0}, {i})) {
				dq.push_back(i);
				chk[i] = true;
				break;
			}
		}
		for (int i = 1; i < N; i++) {
			if (chk[i]) continue;
			if (are_connected({i}, {dq.back()}))
				dq.push_back(i);
			else
				dq.push_front(i);
		}
		return vector<int>(dq.begin(), dq.end());
	}
	vector<int> path = {0};
	vector<int> clique;
	int p = 1;
	while (true) {
		if (!clique.empty() && are_connected({path.back()}, clique)) {
			int s = -1;
			for (int x : clique) {
				if (are_connected({x}, {path.back()})) {
					s = x;
					break;
				}
			}
			path.push_back(s);
			for (int x : clique) if (s != x) {
				path.push_back(x);
			}
			clique.clear();
		}
		else {
			while (p < N && !are_connected({path.back()}, {p})) {
				clique.push_back(p++);
			}
			if (p == N) break;
			path.push_back(p++);
		}
	}
	if (clique.empty() || !are_connected(path, clique)) {
		if (path.size() < clique.size())
			return clique;
		else
			return path;
	}
	auto [u, v] = find_edge(path, clique);
	vector<int> ans;
	for (int x : clique) if (x != v) ans.push_back(x);
	ans.push_back(v);
	bool f = false;
	p = find(path.begin(), path.end(), u) - path.begin();
	for (int i = p; i < path.size(); i++) ans.push_back(path[i]);
	for (int i = 0; i < p; i++) ans.push_back(path[i]);
	return path;
}

컴파일 시 표준 에러 (stderr) 메시지

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:92:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for (int i = p; i < path.size(); i++) ans.push_back(path[i]);
      |                  ~~^~~~~~~~~~~~~
longesttrip.cpp:90:7: warning: unused variable 'f' [-Wunused-variable]
   90 |  bool f = false;
      |       ^

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