제출 #681069

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
681069		QwertyPi	즐거운 행로 (APIO20_fun)	C++14	40 / 100	135 ms	17060 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;
    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 - i - 2){
          while(subtrees[(j + 1) % 3].size()) subtrees[(j + 2) % 3].push(subtrees[(j + 1) % 3].top()), subtrees[(j + 1) % 3].pop();
          if(st == (j + 1) % 3) st = (j + 2) % 3;
          break;
        }
      }
    }
  }
  P.push_back(root);
  return P;
}

컴파일 시 표준 에러 (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++){
      |                    ~~^~~~~~~~~~~~~
fun.cpp:49:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |       for(int j = 0; j < sons.size(); j++){
      |                      ~~^~~~~~~~~~~~~
fun.cpp:50: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]
   50 |         if(subtrees[j].size() * 2 == N - i - 2){
      |            ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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