Submission #927311

#	Time	Username	Problem	Language	Result	Execution time	Memory
927311		TAhmed33	즐거운 행로 (APIO20_fun)	C++17	0 / 100	35 ms	148732 KiB

fun

#include <bits/stdc++.h>
#include "fun.h"
using namespace std;
int adj[17][17];
int dp[17][17][1 << 17];
vector <int> ret;
int n;
int ans (int a, int b, int mask) {
	int &ret = dp[a][b][mask]; if (ret != -1) return ret;
	if (mask == 0) return ret = 1;
	ret = 0;
	for (int i = 0; i < n; i++) {
		if (mask & (1 << i)) {
			if (adj[a][b] >= adj[b][i]) {
				ret |= ans(b, i, mask ^ (1 << i));
			}
		}
	}
	return ret;
}
void reconstruct (int a, int b, int mask) {
	if (mask == 0) return;
	for (int i = 0; i < n; i++) {
		if (mask & (1 << i)) {
			if (adj[a][b] >= adj[b][i]) {
				ret.push_back(i);
				reconstruct(b, i, mask ^ (1 << i));
				return;
			}
		}
	}
}
vector <int> createFunTour (int N, int q) {
	n = N;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			adj[i][j] = hoursRequired(i, j);
		}
	}
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j) continue;
			if (ans(i, j, ((1 << n) - 1) ^ (1 << i) ^ (1 << j))) {
				ret.push_back(i); ret.push_back(j);
				reconstruct(i, j, ((1 << n) - 1) ^ (1 << i) ^ (1 << j));
				return ret;
			}
		}
	}
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:51:1: warning: control reaches end of non-void function [-Wreturn-type]
   51 | }
      | ^

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