Submission #996391

#	Time	Username	Problem	Language	Result	Execution time	Memory
996391		Dan4Life	Fun Tour (APIO20_fun)	C++17	26 / 100	74 ms	16588 KiB

fun

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

#define all(a) begin(a),end(a)
#define sz(a) (int)a.size()
#define pb push_back

const int mxN = (int)1000;
int dis[mxN][mxN];
bool vis[mxN];

vector<int> createFunTour(int N, int Q) {
	vector<int> ans; ans.clear();
	int mx = 0;
	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			dis[i][j] = hoursRequired(i,j), mx=max(mx,dis[i][j]);
	memset(vis,0,sizeof(vis));
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			if(i==j) continue;
			if(dis[i][j]!=mx) continue;
			int x = i; vis[x] = 1; ans.pb(x);
			while(sz(ans)!=N){
				int nx = -1, mx_d=0;
				for(int k = 0; k < N; k++){
					if(vis[k]) continue;
					if(mx_d<dis[x][k]) nx=k, mx_d=dis[x][k];
				}
				x=nx; vis[x] = 1; ans.pb(x);
			}
			return ans;
		}
	}
	return ans;
}

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