oj.uz

Submission #841034

# Submission time Handle Problem Language Result Execution time Memory
841034 2023-09-01T06:18:39 Z jhwest2 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 211 ms 332 KB 
#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 {
					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

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

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 196 ms 208 KB too many calls
2 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 208 KB Output is correct
2 Correct 7 ms 208 KB Output is correct
3 Correct 6 ms 208 KB Output is correct
4 Correct 6 ms 208 KB Output is correct
5 Correct 7 ms 332 KB Output is correct
6 Correct 9 ms 208 KB Output is correct
7 Correct 7 ms 208 KB Output is correct
8 Correct 9 ms 208 KB Output is correct
9 Correct 6 ms 208 KB Output is correct
10 Correct 6 ms 208 KB Output is correct
11 Correct 7 ms 208 KB Output is correct
12 Correct 9 ms 208 KB Output is correct
13 Correct 6 ms 208 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 211 ms 208 KB too many calls
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 122 ms 208 KB too many calls
2 Halted 0 ms 0 KB -