Submission #955167

#	Time	Username	Problem	Language	Result	Execution time	Memory
955167		42kangaroo	Longest Trip (IOI23_longesttrip)	C++17	0 / 100	1 ms	344 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 loopSt = st, loopEn = st, oEnSt = oSt, oEnEn = oSt, oNC = -1;
	g_t gr(N);
	while (!se.empty() || oNC != -1) {
		if (oNC == -1) {
			oNC = se.back();
			se.pop_back();
		} else {
			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;
				}
			}
		}
	}
	if (!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 (!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;
	}
	assert(false);
	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:120:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |   for (int i = 0; i < reLo.size(); ++i) {
      |                   ~~^~~~~~~~~~~~~
longesttrip.cpp:123:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |   for (int i = 0; i < reoEn.size(); ++i) {
      |                   ~~^~~~~~~~~~~~~~

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