oj.uz

Submission #955176

# Submission time Handle Problem Language Result Execution time Memory
955176 2024-03-29T15:04:36 Z 42kangaroo Longest Trip (IOI23_longesttrip) C++17
5 / 100
 15 ms 604 KB 
#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, oNCSt = ncSt, oNCEn = ncSt, ind1 = -1;
	g_t gr(N);
	while (!se.empty() || oNCEn != -1 || ind1 != -1) {
		if (ind1 == -1 && !se.empty()) {
			ind1 = se.back();
			se.pop_back();
		} else {
			if (ind1 == -1) {
				if (are_connected({oEnEn}, {oNCEn})) {
					gr[oEnEn].push_back(oNCEn);
					gr[oNCEn].push_back(oEnEn);
					oEnEn = oNCSt;
					oNCEn = oNCSt = -1;
				} else {
					if (are_connected({oNCEn}, {loopEn})) {
						gr[loopEn].push_back(oNCEn);
						gr[oNCEn].push_back(loopEn);
						loopEn = oNCSt;
						oNCEn = oNCSt = -1;
					} else {
						gr[loopEn].push_back(oEnEn);
						gr[oEnEn].push_back(loopEn);
						loopEn = oEnSt;
						oEnSt = oNCSt;
						oEnEn = oNCEn;
						oNCSt = oNCEn = -1;
					}
				}
			} else {
				if (!are_connected({oEnEn}, {oNCEn, ind1})) {
					gr[ind1].push_back(oNCEn);
					gr[oNCEn].push_back(ind1);
					oNCEn = ind1;
					ind1 = -1;
				} else {
					if (are_connected({oEnEn}, {ind1})) {
						gr[oEnEn].push_back(ind1);
						gr[ind1].push_back(oEnEn);
						oEnEn = ind1;
						ind1 = -1;
					} else {
						gr[oNCEn].push_back(oEnEn);
						gr[oEnEn].push_back(oNCEn);
						oEnEn = oNCSt;
						oNCSt = oNCEn = ind1;
					}
				}
			}
		}
	}
	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

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

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB invalid array
2 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 340 KB Output is correct
2 Correct 12 ms 344 KB Output is correct
3 Correct 11 ms 344 KB Output is correct
4 Correct 9 ms 600 KB Output is correct
5 Correct 11 ms 604 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 344 KB Output is correct
2 Correct 11 ms 344 KB Output is correct
3 Correct 11 ms 344 KB Output is correct
4 Correct 10 ms 344 KB Output is correct
5 Correct 10 ms 600 KB Output is correct
6 Correct 15 ms 344 KB Output is correct
7 Incorrect 1 ms 344 KB invalid array
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 344 KB Output is correct
2 Correct 11 ms 344 KB Output is correct
3 Correct 10 ms 344 KB Output is correct
4 Correct 9 ms 344 KB Output is correct
5 Correct 9 ms 600 KB Output is correct
6 Correct 12 ms 344 KB Output is correct
7 Incorrect 1 ms 344 KB invalid array
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 596 KB Output is correct
2 Correct 13 ms 500 KB Output is correct
3 Correct 10 ms 344 KB Output is correct
4 Correct 10 ms 344 KB Output is correct
5 Partially correct 9 ms 344 KB Output is partially correct
6 Correct 12 ms 344 KB Output is correct
7 Incorrect 1 ms 344 KB invalid array
8 Halted 0 ms 0 KB -