Submission #1201681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201681		A_M_Namdar	Fun Tour (APIO20_fun)	C++20	0 / 100	0 ms	324 KiB

fun

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

const int N = 18;
int d[N][N];
bool dp[N][N][1 << N];
pair<int, int>par[N][N][1 << N];

vector<int> createFunTour(int n, int q) {
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) 
			d[i][j] = hoursRequired(i, j);
	for (int i = 0; i < n; i++) 
		dp[0][i][1 << i] = 1;
	for (int i = 0; i > 0; i--) {
		for (int j = 0; j < n; j++) {
			for (int mask = 0; mask < (1 << n); mask++) {
				if (dp[i][j][mask]) {
					for (int k = 0; k < n; k++) {
						if (((mask >> i) & 1) == 0 && d[j][k] >= i && !dp[d[j][k]][k][mask | (1 << k)]) {
							dp[d[j][k]][k][mask | (1 << k)] = 1;
							par[d[j][k]][k][mask | (1 << k)] = {i, j};
						}
					}
				}
			}
		}
	}
	vector<int> ans;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) 
			if (dp[i][j][(1 << n) - 1]) {
				int mask = (1 << n) - 1;
				while (__builtin_popcount(mask) > 1) {
					ans.push_back(j);
					pair<int, int> tmp = par[i][j][mask];
					mask -= (1 << j);
					i = tmp.first, j = tmp.second;
				}
				ans.push_back(j);
				return ans;
			}
	return ans;
}

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