Submission #982388

#	Time	Username	Problem	Language	Result	Execution time	Memory
982388		Marcus	Fun Tour (APIO20_fun)	C++17	10 / 100	281 ms	524288 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#include <vector>
int n, q;
vector<vector<int>> adj(1e5);
 
std::vector<int> createFunTour(int N, int Q) {
  n=N; q=Q;
  vector<vector<int>> dist(n, vector<int>(n, -1));
  for (int i=0; i<n; i++)
  {
    for (int j=0; j<n; j++)
    {
        dist[i][j] = hoursRequired(i, j);
    }
  }
  vector<vector<pair<int, int>>> dp((1<<n), vector<pair<int, int>> (n));
  for (int i=0; i<n; i++) {dp[1<<i][i] = {1e5+1, -1};}
  for (int s=1; s<(1<<n); s++)
  {
    for (int i=0; i<n; i++)
    {
        if (!(s & (1<<i))) continue;
        for (int j=0; j<n; j++)
        {
            if (!(s & (1<<j)) || i == j) continue;
            int prev = (s^(1<<i));
            if (dp[prev][j].first != 0 && dist[i][j] <= dp[prev][j].first) 
            {
                if (dp[s][i].first < dist[i][j]) {dp[s][i] = {dist[i][j], j};}
            }
        }
    }
  }
  vector<int> answer;
  int s = (1<<n)-1;
  pair<int, int> chain;
  for (int i=0; i<n; i++) {if (dp[s][i].first) {chain = dp[s][i]; answer.push_back(i); break;}}
  while (s)
  {
    s = (s^(1<<(answer.back())));
    if (chain.second != -1) answer.push_back(chain.second);
    chain = dp[s][chain.second];
  }
  reverse(answer.begin(), answer.end());
  return answer;
}

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