Submission #1175837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175837		Muhammet	Fun Tour (APIO20_fun)	C++20	10 / 100	2096 ms	2376 KiB

fun

#include "bits/stdc++.h"
#include "fun.h"
// #include "grader.cpp"

using namespace std;

const int N1 = 1e3 + 5;

int dis[N1][N1], n;

vector <int> v, ans;

void f(int x, int k, int mask) {
    v.push_back(x);
    if(mask == (1<<n)-1) {
        ans = v;
    }
    for(int i = 0; i < n; i++) {
        if(!(mask & (1<<i)) and dis[x][i] <= k) {
            f(i, dis[x][i], mask | (1<<i));
        }
    }
    v.pop_back();
}

vector<int> createFunTour(int N, int q) {
    n = N;
  // int H = hoursRequired(0, N - 1);
  // int A = attractionsBehind(0, N - 1);
    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            dis[i][j] = dis[j][i] = hoursRequired(i, j);
            // if(dis[i][j] == 1) v[i].push_back(j), v[j].push_back(i);
        }
    }
    for(int i = 0; i < n; i++) {
        f(i, n, 1<<i);
        if((int)ans.size()) {
            return ans;
        }
    }
    return {-1};
    // return vector<int>(n, 0);
}

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