Submission #1304675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304675		vtnoo	Fun Tour (APIO20_fun)	C++20	26 / 100	8 ms	1604 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,pao=b;i<pao;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int MAXN=505;
int d[MAXN][MAXN];
int getDist(int a,int b){
	if(d[a][b]!=-1)return d[a][b];
	else return d[a][b]=d[b][a]=hoursRequired(a,b);
}
std::vector<int> createFunTour(int N, int Q) {
	mset(d,-1);
	vector<bool>already(N,false);
	fore(i,0,N)d[i][i]=0;
	fore(i,1,N){
		d[0][i]=getDist(0,i);
	}
	pair<int,int>a={-1,0};
	fore(i,1,N){
		a=max(a,{d[0][i],i});
	}
	fore(i,0,N){
		if(i!=a.snd){
			d[a.snd][i]=getDist(a.snd,i);
		}
	}
	pair<int,int>b={-1,0};
	fore(i,0,N){
		b=max(b,{d[a.snd][i],i});
	}
	vector<int>p;
	p.pb(a.snd);p.pb(b.snd);
	already[p[0]]=already[p[1]]=true;
	while(SZ(p)<N){
		pair<int,int>c={-1,0};
		fore(i,0,N){	
			if(!already[i]){
				c=max(c,{getDist(p.back(),i),i});
			}
		}
		p.pb(c.snd);
		already[c.snd]=true;
	}
	return p;
}

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