Submission #699478

#	Time	Username	Problem	Language	Result	Execution time	Memory
699478		cig32	Fun Tour (APIO20_fun)	C++17	0 / 100	1 ms	304 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;
  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;
      }
    }
  }
  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];
  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});
  }
  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;
    }
  }
  ans.push_back(depths[id].top().second);
  depths[id].pop();
  for(int i=0; i<N-1; i++) {
    ma = -1;
    int id2;
    for(int j=0; j<M; j++) {
      if((int) (depths[j].size()) > ma) {
        ma = depths[j].size();
        id2 = j;
      }
    }
    if(id == id2) {
      ma = -1;
      for(int j=0; j<M; j++) {
        if(j != id && depths[j].size() && depths[j].top().first > ma) {
          ma = depths[j].top().first;
          id2 = j;
        }
      }
    }
    ans.push_back(depths[id2].top().second);
    depths[id2].pop();
    id = id2;
  }
  return ans;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:60:5: warning: 'id2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |     if(id == id2) {
      |     ^~
fun.cpp:42:7: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   42 |   int id;
      |       ^~
fun.cpp:20:49: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   20 |   for(int i=0; i<N; i++) dist[i] = hoursRequired(rt, i);
      |                                    ~~~~~~~~~~~~~^~~~~~~

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