Submission #568722

#	Time	Username	Problem	Language	Result	Execution time	Memory
568722		_karan_gandhi	Fun Tour (APIO20_fun)	C++17	26 / 100	121 ms	25320 KiB

fun

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

#define ll long long
#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "

template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "[" << p.first << ", " << p.second << "]"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) { cout << "["; for(int i = 0; i < (int)v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) { cin >> p.first; return cin >> p.second; }

std::vector<int> createFunTour(int n, int Q) {
	vector<vector<pair<int, int>>> distances(n);

	int diameter = 0;
	int a, b;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			int d = hoursRequired(i, j);
			if (d > diameter) {
				a = i;
				b = j;
				diameter = d;
			}
			distances[i].emplace_back(d, j);
			distances[j].emplace_back(d, i);
		}
	}

	// cout << pl(a) << pl(b) << endl;

	vector<int> ans;
	ans.push_back(b);
	ans.push_back(a);
	int u = a;

	// cout << pl(u) << endl;
	// cout << pl(distances[u]) << endl;
	for (int i = 0; i < n; i++) {
		sort(all(distances[i]));
		reverse(all(distances[i]));
	}
	vector<bool> vis(n, 0);
	vis[a] = vis[b] = 1;
	while (ans.size() != n) {
		// cout << pl(u) << endl;
		for (auto [d, v] : distances[u]) {
			if (!vis[v]) {
				ans.push_back(v);
				vis[v] = 1;
				u = v;
				break;
			}
		}
	}

	assert(ans.size() == n);
	// cout << ans << endl;
	return ans;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:47:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |  while (ans.size() != n) {
      |         ~~~~~~~~~~~^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from fun.cpp:2:
fun.cpp:59:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |  assert(ans.size() == n);
      |         ~~~~~~~~~~~^~~~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34