Submission #965703

#	Time	Username	Problem	Language	Result	Execution time	Memory
965703		pcc	Fun Tour (APIO20_fun)	C++17	26 / 100	76 ms	14680 KiB

fun

#include "fun.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;

/*
  int H = hoursRequired(0, N - 1);
  int A = attractionsBehind(0, N - 1);
  return std::vector<int>(N);
*/

const int mxn = 550;
vector<int> tree[mxn];
int dist[mxn];
bitset<mxn> del;
vector<int> ans;

void dfs(int now,int par){
	for(auto nxt:tree[now]){
		if(nxt == par||del[nxt])continue;
		dist[nxt] = dist[now]+1;
		dfs(nxt,now);
	}
	return;
}

std::vector<int> createFunTour(int N, int Q) {
	for(int i = 0;i<N;i++){
		for(int j = i+1;j<N;j++){
			if(hoursRequired(i,j) == 1){
				tree[i].push_back(j);
				tree[j].push_back(i);
			}
		}
	}
	dfs(1,1);
	int now = max_element(dist,dist+N)-dist;
	ans.push_back(now);
	while(ans.size()<N){
		memset(dist,-1,sizeof(dist));
		dist[now] = 0;
		dfs(now,now);
		del[now] = true;
		now = max_element(dist,dist+N)-dist;
		ans.push_back(now);
	}
	return ans;
}

Compilation message (stderr)

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

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