Submission #728994

#	Time	Username	Problem	Language	Result	Execution time	Memory
728994		stevancv	Fun Tour (APIO20_fun)	C++14	26 / 100	93 ms	16720 KiB

fun

#include <bits/stdc++.h>
#include "fun.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int inf = 2e9;
vector<int> createFunTour(int n, int q) {
    if (n <= 500) {
        vector<vector<int>> g(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (hoursRequired(i, j) == 1) {
                    g[i].push_back(j);
                    g[j].push_back(i);
                }
            }
        }
        vector<int> ans;
        vector<int> bia(n);
        int tko = 0;
        while (ans.size() < n) {
            queue<int> q;
            vector<int> dist(n, inf);
            q.push(tko);
            dist[tko] = 0;
            while (!q.empty()) {
                int s = q.front(); q.pop();
                for (int u : g[s]) {
                    if (dist[u] > dist[s] + 1) {
                        dist[u] = dist[s] + 1;
                        q.push(u);
                    }
                }
            }
            int mx = tko;
            for (int i = 0; i < n; i++) {
                if (bia[i] == 0 && dist[i] > dist[mx]) mx = i;
            }
            ans.push_back(mx);
            bia[mx] = 1;
            tko = mx;
        }
        return ans;
    }
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:26:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |         while (ans.size() < n) {
      |                ~~~~~~~~~~~^~~
fun.cpp:50:1: warning: control reaches end of non-void function [-Wreturn-type]
   50 | }
      | ^

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