Submission #955188

#	Time	Username	Problem	Language	Result	Execution time	Memory
955188		42kangaroo	Longest Trip (IOI23_longesttrip)	C++17	85 / 100	15 ms	980 KiB

longesttrip

#include "longesttrip.h"
#include "bits/stdc++.h"

using g_t = std::vector<std::vector<int>>;

std::vector<int> longest_trip(int N, int D) {
	using namespace std;
	vector<int> se(N);
	std::iota(se.begin(), se.end(), 0);
	std::random_device rd;
	std::mt19937 g(rd());
	shuffle(se.begin(), se.end(), g);
	int st = se.back();
	se.pop_back();
	int oSt = se.back();
	se.pop_back();
	int ncSt = se.back();
	se.pop_back();
	int loopSt = st, loopEn = st, oEnSt = oSt, oEnEn = oSt, oNC = ncSt, ind1 = -1;
	g_t gr(N);
	while (!se.empty() || oNC != -1 || ind1 != -1) {
		if (oNC == -1 && !se.empty()) {
			oNC = se.back();
			se.pop_back();
		} else if (ind1 == -1 && !se.empty()) {
			ind1 = se.back();
			se.pop_back();
		} else {
			if (ind1 == -1) {
				if (are_connected({oEnEn}, {oNC})) {
					gr[oEnEn].push_back(oNC);
					gr[oNC].push_back(oEnEn);
					oEnEn = oNC;
					oNC = -1;
				} else {
					if (are_connected({oNC}, {loopEn})) {
						gr[loopEn].push_back(oNC);
						gr[oNC].push_back(loopEn);
						loopEn = oNC;
						oNC = -1;
					} else {
						gr[loopEn].push_back(oEnEn);
						gr[oEnEn].push_back(loopEn);
						loopEn = oEnSt;
						oEnSt = oNC;
						oEnEn = oNC;
						oNC = -1;
					}
				}
			} else {
				if (!are_connected({oEnEn}, {oNC, ind1})) {
					gr[oNC].push_back(ind1);
					gr[ind1].push_back(oNC);
					if (are_connected({oNC}, {loopEn})) {
						gr[loopEn].push_back(oNC);
						gr[oNC].push_back(loopEn);
						loopEn = ind1;
						oNC = ind1 = -1;
					} else {
						gr[loopEn].push_back(oEnEn);
						gr[oEnEn].push_back(loopEn);
						loopEn = oEnSt;
						oEnSt = ind1;
						oEnEn = oNC;
						oNC = ind1 = -1;
					}
				} else {
					if (are_connected({oEnEn}, {oNC})) {
						gr[oEnEn].push_back(oNC);
						gr[oNC].push_back(oEnEn);
						oEnEn = oNC;
						oNC = ind1;
						ind1 = -1;
					} else {
						gr[oEnEn].push_back(ind1);
						gr[ind1].push_back(oEnEn);
						oEnEn = ind1;
						ind1 = -1;
					}
				}
			}
		}

	}
	if (loopSt != loopEn && !are_connected({loopSt}, {loopEn})) {
		if (are_connected({loopEn}, {oEnEn})) {
			gr[loopEn].push_back(oEnEn);
			gr[oEnEn].push_back(loopEn);
			loopEn = oEnSt;
		} else {
			gr[loopSt].push_back(oEnEn);
			gr[oEnEn].push_back(loopSt);
			loopSt = oEnSt;
		}
	} else if (oEnEn != oEnSt && !are_connected({oEnEn}, {oEnSt})) {
		if (are_connected({loopEn}, {oEnEn})) {
			gr[loopEn].push_back(oEnEn);
			gr[oEnEn].push_back(loopEn);
			loopEn = oEnSt;
		} else {
			gr[loopEn].push_back(oEnSt);
			gr[oEnSt].push_back(loopEn);
			loopEn = oEnEn;
		}
	} else {
		int act = loopSt;
		vector<int> reLo{{act}};
		if (!gr[act].empty()) {
			act = gr[act][0];
			while (true) {
				int ne = gr[act][0];
				if (ne == reLo.back() && gr[act].size() > 1) ne = gr[act][1];
				reLo.push_back(act);
				if (gr[act].size() == 1) {
					break;
				}
				act = ne;
			}
		}
		act = oEnSt;
		vector<int> reoEn{{act}};
		if (!gr[act].empty()) {
			act = gr[act][0];
			while (true) {
				int ne = gr[act][0];
				if (ne == reoEn.back() && gr[act].size() > 1) ne = gr[act][1];
				reoEn.push_back(act);
				if (gr[act].size() == 1) {
					break;
				}
				act = ne;
			}
		}
		if (!are_connected(reLo, reoEn)) {
			if (reLo.size() > reoEn.size()) return reLo;
			return reoEn;
		}
		int l = 0, r = reoEn.size();
		while (l + 1 < r) {
			int m = (l + r) / 2;
			vector<int> relv;
			for (int i = l; i < m; ++i) {
				relv.push_back(reoEn[i]);
			}
			if (are_connected(relv, reLo)) r = m;
			else l = m;
		}
		int ll = 0, rr = reLo.size();
		while (ll + 1 < rr) {
			int m = (ll + rr) / 2;
			vector<int> relv;
			for (int i = ll; i < m; ++i) {
				relv.push_back(reLo[i]);
			}
			if (are_connected({reoEn[l]}, relv)) rr = m;
			else ll = m;
		}
		vector<int> res;
		for (int i = 0; i < reLo.size(); ++i) {
			res.push_back(reLo[(ll + 1 + i) % reLo.size()]);
		}
		for (int i = 0; i < reoEn.size(); ++i) {
			res.push_back(reoEn[(l + i) % reoEn.size()]);
		}
		return res;
	}
	int act = loopSt;
	vector<int> res{{act}};
	if (!gr[act].empty()) {
		act = gr[act][0];
		while (true) {
			int ne = gr[act][0];
			if (ne == res.back() && gr[act].size() > 1) ne = gr[act][1];
			res.push_back(act);
			if (gr[act].size() == 1) {
				break;
			}
			act = ne;
		}
	}
	return res;
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:159:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |   for (int i = 0; i < reLo.size(); ++i) {
      |                   ~~^~~~~~~~~~~~~
longesttrip.cpp:162:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |   for (int i = 0; i < reoEn.size(); ++i) {
      |                   ~~^~~~~~~~~~~~~~

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