Submission #1204137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204137		siewjh	Longest Trip (IOI23_longesttrip)	C++20	100 / 100	6 ms	416 KiB

longesttrip

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

vector<int> longest_trip(int N, int D){
	vector<int> v1 = {0}, v2 = {1};
	bool gnc = 0;
	for (int i = 2; i < N; i++){
		if (gnc){
			if (are_connected({v1.back()}, {i})){
				v1.push_back(i); gnc = 0;
			}
			else{
				v2.push_back(i); gnc = 1;
			}
		}
		else{
			if (are_connected({v1.back()}, {i})){
				v1.push_back(i); gnc = 0;
			}
			else if (are_connected({v2.back()}, {i})){
				v2.push_back(i); gnc = 1;
			}
			else{
				if (i + 1 < N){
					bool conn = are_connected({i}, {i + 1});
					if (!conn) v1.push_back(i + 1);
					for (int j = v2.size() - 1; j >= 0; j--) v1.push_back(v2[j]);
					v2 = {i};
					if (conn) v2.push_back(i + 1);
					i++;
				}
				else{
					for (int j = v2.size() - 1; j >= 0; j--) v1.push_back(v2[j]);
					v2 = {i};
				}
				gnc = 0;
			}
		}
	}
	if (!are_connected(v1, v2)) return (v1.size() >= v2.size() ? v1 : v2);
	vector<int> qv1 = {v1[0]}, qv2 = {v2[0]};
	if (v1.size() != 1) qv1.push_back(v1.back());
	if (v2.size() != 1) qv2.push_back(v2.back());
	if (are_connected(qv1, qv2)){
		int v1e;
		if (are_connected({v1.back()}, qv2)) v1e = v1.back();
		else{
			v1e = v1[0]; reverse(v1.begin(), v1.end());
		}
		if (are_connected({v1e}, {v2.back()})) reverse(v2.begin(), v2.end());
		for (int x : v2) v1.push_back(x);
		return v1;
	}
	int lo = 0, hi = v1.size() - 1;
	while (lo < hi){
		int m = (lo + hi) >> 1;
		vector<int> qv;
		for (int i = lo; i <= m; i++) qv.push_back(v1[i]);
		if (are_connected(qv, v2)) hi = m;
		else lo = m + 1;
	}
	int c1 = hi;
	lo = 0, hi = v2.size() - 1;
	while (lo < hi){
		int m = (lo + hi) >> 1;
		vector<int> qv;
		for (int i = lo; i <= m; i++) qv.push_back(v2[i]);
		if (are_connected({v1[c1]}, qv)) hi = m;
		else lo = m + 1;
	}
	int c2 = hi;
	vector<int> ans;
	for (int i = c1 - 1; i >= 0; i--) ans.push_back(v1[i]);
	for (int i = v1.size() - 1; i >= c1; i--) ans.push_back(v1[i]);
	for (int i = c2; i >= 0; i--) ans.push_back(v2[i]);
	for (int i = v2.size() - 1; i > c2; i--) ans.push_back(v2[i]);
	return ans;
}

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