Submission #735368

#	Time	Username	Problem	Language	Result	Execution time	Memory
735368		keisuke6	Fun Tour (APIO20_fun)	C++14	26 / 100	90 ms	16720 KiB

fun

#include "fun.h"

#include <iostream>
#include <queue>
#include <vector>
#include <set>
using namespace std;
std::vector<int> createFunTour(int N, int Q) {
  vector<vector<int>> G(N);
  for(int i=0;i<N;i++)for(int j=0;j<N;j++){
    int a_ = hoursRequired(i, j);
    if(a_ == 1) G[i].push_back(j);
  }
  queue<int> q;
  q.push(0);
  vector<int> dist(N,1e9);
  dist[0] = 0;
  while(!q.empty()){
    int pos = q.front();
    q.pop();
    for(int x:G[pos]){
      if(dist[x] != 1e9) continue;
      q.push(x);
      dist[x] = dist[pos] + 1;
    }
  }
  int now = 0, best = 0;
  for(int i=0;i<N;i++)if(best < dist[i]){
    best = dist[i];
    now = i;
  }
  vector<int> A = {};
  set<int> s;
  while(A.size() != N){
    for(int i=0;i<N;i++) dist[i] = 1e9;
    A.push_back(now);
    s.insert(now);
    q.push(now);
    dist[now] = 0;
    while(!q.empty()){
      int pos = q.front();
      q.pop();
      for(int x:G[pos]){
        if(dist[x] != 1e9) continue;
        q.push(x);
        dist[x] = dist[pos] + 1;
      }
    }
    best = 0;
    for(int i=0;i<N;i++)if(best < dist[i] && !s.count(i)){
      best = dist[i];
      now = i;
    }
  }
  return A;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:34:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |   while(A.size() != N){
      |         ~~~~~~~~~^~~~

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