Submission #1193498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193498		omsincoconut	Fun Tour (APIO20_fun)	C++17	26 / 100	287 ms	589824 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> createFunTour(int N, int Q) {
    int dist[N][N];
    for (int i = 0; i < N; i++) {
        dist[i][i] = 0;
        for (int j = i+1; j < N; j++) {
            dist[i][j] = dist[j][i] = hoursRequired(i, j);
        }
    }

    vector<int> ret(N);
    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            if (dist[ret[0]][ret[1]] < dist[i][j]) {
                ret[0] = i;
                ret[1] = j;
            }
        }
    }

    vector<bool> vis(N);
    vis[ret[0]] = vis[ret[1]] = true;
    for (int i = 2; i < N; i++) {
        int cur = ret[i-1];
        for (int j = 0; j < N; j++) {
            if (!vis[j] && dist[ret[i-1]][j] > dist[ret[i-1]][cur]) {
                cur = j;
            }
        }
        ret[i] = cur;
        vis[ret[i]] = true;
    }

    return ret;
}

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