Submission #841035

#	Time	Username	Problem	Language	Result	Execution time	Memory
841035		jhwest2	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	18 ms	392 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;
			if (clique.size() == 1) {
				s = clique[0];
			}
			else {
				s = find_edge({path.back()}, clique).second;
			}
			path.push_back(s);
			for (int x : clique) if (s != x) {
				path.push_back(x);
			}
			clique.clear();
		}
		else {
			while (p < N) {
				if (p == N - 1) {
					if (!are_connected({path.back()}, {p})) {
						clique.push_back(p++);
					}
					else break;
				}
				else {
					if (!are_connected({path.back()}, {p, p + 1})) {
						clique.push_back(p++);
						clique.push_back(p++);
					}
					else {
						if (!are_connected({path.back()}, {p}))
							++p;
						
						break;
					}
				}
			}
			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;
	}
	if (!clique.empty() && are_connected({path[0]}, clique)) {
		auto [u, v] = find_edge({path[0]}, clique);
		vector<int> ans;
		for (int x : clique) if (x != v) ans.push_back(x);
		ans.push_back(v);
		for (int x : path) ans.push_back(x);
		return ans;
	}
	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);
	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 ans;
}

Compilation message (stderr)

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

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