Submission #982232

#	Time	Username	Problem	Language	Result	Execution time	Memory
982232		Marcus	Fun Tour (APIO20_fun)	C++17	0 / 100	10 ms	4196 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<int>> dp((1<<n), vector<int>(n, 0));
  for (int i=0; i<n; i++) {dp[1<<i][i] = 1e5+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))) continue;
            int prev = (s^(1<<i));
            if (dist[i][j] <= dp[prev][j]) dp[s][i] = max(dp[s][i], dist[i][j]);
        }
    }
  }
  int s = (1<<n)-1;
  vector<int> answer;
  int cnt = 0;
  while (s)
  {
    for (int i=0; i<n; i++)
    {
        if (dp[s][i] != 0 && (s&(1<<i))) {
            answer.push_back(i);
            s = (s^(1<<i));
            break;
        }
    }
  }
  reverse(answer.begin(), answer.end());
  return answer;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:35:7: warning: unused variable 'cnt' [-Wunused-variable]
   35 |   int cnt = 0;
      |       ^~~

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