Submission #681052

#	Time	Username	Problem	Language	Result	Execution time	Memory
681052		QwertyPi	Fun Tour (APIO20_fun)	C++14	47 / 100	116 ms	17096 KiB

fun

#include "fun.h"
#define fi first
#define se second
#include <bits/stdc++.h>

using namespace std;

vector<int> createFunTour(int N, int Q) {

  vector<int> dep(N), sz(N);
  for(int i = 0; i < N; i++){
    sz[i] = attractionsBehind(0, i);
  }
  int root = 0;
  for(int i = 0; i < N; i++){
    if(sz[i] <= sz[root] && sz[i] >= (N + 1) / 2) root = i;
  }
  vector<int> sons;
  priority_queue<pair<int, int>> subtrees[3];
  for(int i = 0; i < N; i++){
    dep[i] = hoursRequired(root, i);
  }
  for(int i = 0; i < N; i++){
    if(dep[i] == 1) sons.push_back(i);
  }
  for(int i = 0; i < N; i++){
    if(i == root) continue;
    int in_subtree = (int) sons.size() - 1;
    for(int j = 0; j < (int) sons.size() - 1; j++){
      if(hoursRequired(sons[j], i) == dep[i] - dep[sons[j]]){
        in_subtree = j;
      }
    }
    subtrees[in_subtree].push({dep[i], i});
  }

  vector<int> P;
  int _pv = -1;
  for(int i = 0; i < N - 1; i++){
    int mx = -1, st = -1;
    for(int j = 0; j < sons.size(); j++){
      if(_pv == j) continue;
      if(subtrees[j].size() && subtrees[j].top().fi >= mx){
        mx = subtrees[j].top().fi, st = j;
      }
    }
    P.push_back(subtrees[st].top().se); subtrees[st].pop(); _pv = st;
  }
  P.push_back(root);
  return P;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int j = 0; j < sons.size(); j++){
      |                    ~~^~~~~~~~~~~~~

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