Submission #560533

#	Time	Username	Problem	Language	Result	Execution time	Memory
560533		piOOE	Fun Tour (APIO20_fun)	C++17	10 / 100	260 ms	524288 KiB

fun

#include "fun.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) begin(x), end(x)

vector<int> createFunTour(int n, int q) {
    const int infI = 1e9 + 7;
    vector<vector<int>> dist(n, vector<int>(q));
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            dist[i][j] = dist[j][i] = hoursRequired(i, j);
        }
    }
    int N = (1 << n);
    vector<vector<int>> dp(N, vector<int>(n, infI)), p(N, vector<int>(n, -1));
    for (int mask = 1; mask < N; ++mask) {
        vector<int> now;
        for (int i = 0; i < n; ++i) {
            if ((mask >> i) & 1) {
                now.push_back(i);
            }
        }
        if (now.size() == 1) {
            dp[mask][now[0]] = 0;
            p[mask][now[0]] = -1;
        } else {
            for (int i : now) {
                int msk = mask ^ (1 << i);
                for (int j : now) {
                    if (i != j) {
                        if (dp[msk][j] <= dist[i][j] && dp[mask][i] > dist[i][j]) {
                            dp[mask][i] = dist[i][j];
                            p[mask][i] = j;
                        }
                    }
                }
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        if (dp[N - 1][i] != infI) {
            vector<int> ans;
            int mask = N - 1;
            while (i != -1) {
                ans.push_back(i);
                int msk = mask ^ (1 << i);
                i = p[mask][i];
                mask = msk;
            }
            return ans;
        }
    }
    assert(false);
    return {};
}

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