Submission #743707

#	Time	Username	Problem	Language	Result	Execution time	Memory
743707		speedyArda	Fun Tour (APIO20_fun)	C++14	10 / 100	940 ms	299976 KiB

fun

#include "fun.h"
#include <vector>
#include "bits/stdc++.h"

using namespace std;
const int BIT = 18;
pair<int, vector<int> > dp[(1 << BIT)][BIT];
int dist[BIT][BIT];
vector<int> createFunTour(int N, int Q) {
  vector<int> ans(N);
  for(int i = 0; i < N; i++)
  {
    dp[(1 << i)][i] = {1e9, {i}};
  }
  for(int i = 1; i < (1 << N); i++)
  {

    for(int a = 0; a < BIT; a++)
    {
      if(dp[i][a].first == 1e9)
        continue;
      if((1 << a) & i)
      {
        for(int l = 0; l < BIT; l++) {
          if(l == a)
            continue;
          if((1 << l) & i) {
              int hour = dist[a][l];
              if(hour == 0) {
                hour = hoursRequired(a, l);
                dist[a][l] = dist[l][a] = hour;
              }
              
              if(dp[i ^ (1 << a)][l].first >= hour)
              {
                vector<int> temp = dp[i ^ (1 << a)][l].second;
                temp.push_back(a);
                dp[i][a] = max(dp[i][a], {hour, temp});
              }
          }
        }
      }
    }
  }
  //for(int i = 0; i < dp[(1 << N) - 1].second.size(); i++)
    //cout << dp[(1 << N) - 1].second[i] << "\n";
  int idx = 0;
  for(int i = 0; i < N; i++)
  {
    if(dp[(1 << N) - 1][i].second.size() == N)
      idx = i;
  }
  return dp[(1 << N) - 1][idx].second;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:50:42: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |     if(dp[(1 << N) - 1][i].second.size() == N)
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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