Submission #699491

#	Time	Username	Problem	Language	Result	Execution time	Memory
699491		cig32	Fun Tour (APIO20_fun)	C++17	31 / 100	131 ms	17056 KiB

fun

#include "bits/stdc++.h"
#include "fun.h"
using namespace std;

#include <vector>

std::vector<int> createFunTour(int N, int Q) {
  if(N == 2) return {0, 1};
  int rt=-1;
  int ma=-1;
  for(int i=0; i<N; i++) {
    int ab = attractionsBehind(0, i);
    if(N - ab <= N/2) {
      if(N - ab > ma) {
        ma=N - ab, rt=i;
      }
    }
  }
  assert(rt>=0);
  int dist[N];
  for(int i=0; i<N; i++) dist[i] = hoursRequired(rt, i);
  vector<int> leader;
  int M = 0;
  for(int i=0; i<N; i++) {
    if(dist[i] == 1) {
      M++;
      leader.push_back(i);
    }
  }
  priority_queue<pair<int, int> > depths[M];
  //cout << rt << "\n";
  vector<int> list[M];
  for(int i=0; i<N; i++) {
    int grp = M-1;
    for(int j=0; j<M-1; j++) {
      int hr = hoursRequired(leader[j], i);
      if(hr + 1 == dist[i]) {
        grp = j; break;
      }
    }
    depths[grp].push({dist[i], i});
    list[grp].push_back(dist[i]);
    //cout << "node " << i <<": group "<<grp<<"\n";
  }
  for(int i=0; i<M; i++) sort(list[i].begin(), list[i].end());
  //for(int i=0; i<M; i++) {
  //  for(int x: list[i]) cout << x << " ";
  //  cout << "\n";
  //}
  vector<int> ans;
  ma = -1;
  int id;
  for(int i=0; i<M; i++) {
    if((int) (depths[i].size()) > ma) {
      ma = depths[i].size();
      id = i;
    }
  }
  if(depths[id].size() <= N/2) {
    ma = -1;
    for(int j=0; j<M; j++) {
      if(depths[j].empty()) continue;
      if(depths[j].top().first > ma) {
        ma = depths[j].top().first, id = j;
      }
    }
  }
  ans.push_back(depths[id].top().second);
  depths[id].pop();
  //cout << ans[0] << " ";
  for(int i=0; i<N-1; i++) {
    ma = -1;
    int id2;
    for(int j=0; j<M; j++) {
      if(j == id) continue;
      int sz = depths[j].size();
      if(sz > ma) {
        ma = sz, id2 = j;
      }
    }
    if(depths[id2].size() <= (N-i-1) / 2) {
      ma = -1;
      for(int j=0; j<M; j++) {
        if(j == id) continue;
        if(depths[j].empty()) continue;
        if(depths[j].top().first > ma) {
          ma = depths[j].top().first, id2 = j;
        }
      }
    }
    ans.push_back(depths[id2].top().second);
    depths[id2].pop();
    id = id2;
    //cout << ans[i+1] << " ";
  }
  //cout << "\n";
  return ans;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:59:24: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |   if(depths[id].size() <= N/2) {
      |      ~~~~~~~~~~~~~~~~~~^~~~~~
fun.cpp:81:27: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |     if(depths[id2].size() <= (N-i-1) / 2) {
      |        ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
fun.cpp:52:7: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |   int id;
      |       ^~
fun.cpp:73:9: warning: 'id2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |     int id2;
      |         ^~~

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