Submission #1201690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201690		A_M_Namdar	Fun Tour (APIO20_fun)	C++20	0 / 100	158 ms	131508 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];
/*
int hoursRequired(int u, int v) {
	int tmp[N];
	memset(tmp, 63, sizeof tmp);
	vector<int> adj[N];
	adj[0] = {1, 5, 6};
	adj[1] = {0, 2, 4};
	adj[2] = {1, 3};
	adj[3] = {2};
	adj[4] = {1};
	adj[5] = {0};
	adj[6] = {0};
	tmp[u] = 0;
	queue<int> q;
	q.push(u);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int y: adj[x]) 
			if (tmp[y] > tmp[x] + 1) {
				tmp[y] = tmp[x] + 1;
				q.push(y);
			}
	}
	return tmp[v];
}*/

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 < n; 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 >> k) & 1) == 0 && d[j][k] >= i) {
							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