Submission #678651

#	Time	Username	Problem	Language	Result	Execution time	Memory
678651		Dan4Life	Fun Tour (APIO20_fun)	C++17	26 / 100	70 ms	1392 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define SZ(a) (int)a.size()

const int maxn = (int)5e2+10;
const int INF = (int)1e9;

vector<int> adj[maxn];
int dis[maxn][maxn];
bool vis[maxn];
int cur = 0;

void dfs(int s, int p){
	if(p!=-1) dis[cur][s] = dis[cur][p]+1;
	for(auto u : adj[s])
		if(u!=p) dfs(u,s);
}
/*
7 400000
0 1
0 5
0 6
1 2
1 4
2 3
*/
vector<int> createFunTour(int n, int q) {
	//int H = hoursRequired(0, N - 1);
	//int A = attractionsBehind(0, N - 1);
	vector<int> ans(n,0);
	for(int i = 0; i < n; i++) adj[i].clear();
	for(int i = 0; i < n; i++)
		for(int j = i+1; j < n; j++)
			if(hoursRequired(i,j)==1) 
				adj[i].pb(j), adj[j].pb(i);
	for(int i = 0; i < n; i++) cur=i, dfs(i,-1);
	for(int i = 0; i < n; i++){
		int mx_dis = 0, use = -1, st = i;
		vector<int> v; v.clear();
		fill(vis,vis+maxn,false);
		vis[st] = 1; v.pb(st); 
		int last_dis = INF, _ = n;
		while(_--){
			use=-1; mx_dis = 0;
			for(int j = 0; j < n; j++){
				if(vis[j]) continue;
				if(mx_dis<dis[st][j] and dis[st][j]<=last_dis) 
					mx_dis = dis[st][j], use=j;
			}
			if(use==-1){ if(SZ(v)==n) return v; break; }
			last_dis = mx_dis, st = use; v.pb(use); vis[use]=1;
		}
	}
	return ans;
}

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