Submission #681130

#	Time	Username	Problem	Language	Result	Execution time	Memory
681130		QwertyPi	Fun Tour (APIO20_fun)	C++14	100 / 100	246 ms	21744 KiB

fun

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

using namespace std;

int tp(priority_queue<pair<int, int>>& pq){
  return !pq.size() ? 0 : pq.top().fi;
}

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++){
    if(sons.size() == 3 && !subtrees[0].empty() && !subtrees[1].empty() && !subtrees[2].empty()){
      for(int j = 0; j < sons.size(); j++){
        if(subtrees[j].size() * 2 >= N - 1 - i && (_pv == j || _pv != j && tp(subtrees[_pv]) >= tp(subtrees[3 - _pv - j]))){
          while(subtrees[(j + 1) % 3].size()) subtrees[(j + 2) % 3].push(subtrees[(j + 1) % 3].top()), subtrees[(j + 1) % 3].pop();
          if(_pv == (j + 1) % 3) _pv = (j + 2) % 3;
          break;
        }
      }
    }
    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;
      }
    }
    if(st == -1){
      P.push_back(root);
      for(int j = 0; j < sons.size(); j++){
        if(subtrees[j].size()) {
          P.push_back(subtrees[j].top().se);
          return P;
        }
      }
    }
    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:44:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |       for(int j = 0; j < sons.size(); j++){
      |                      ~~^~~~~~~~~~~~~
fun.cpp:45:35: 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]
   45 |         if(subtrees[j].size() * 2 >= N - 1 - i && (_pv == j || _pv != j && tp(subtrees[_pv]) >= tp(subtrees[3 - _pv - j]))){
      |            ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
fun.cpp:45:73: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   45 |         if(subtrees[j].size() * 2 >= N - 1 - i && (_pv == j || _pv != j && tp(subtrees[_pv]) >= tp(subtrees[3 - _pv - j]))){
      |                                                                ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fun.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int j = 0; j < sons.size(); j++){
      |                    ~~^~~~~~~~~~~~~
fun.cpp:61:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |       for(int j = 0; j < sons.size(); j++){
      |                      ~~^~~~~~~~~~~~~

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