제출 #566390

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
566390		zaneyu	즐거운 행로 (APIO20_fun)	C++14	26 / 100	69 ms	34972 KiB

fun

#include "fun.h"

#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define REP1(i,n) for(int i=1;i<=n;i++)
using namespace std;
const int maxn=1e3+5;
#define REP(i,n) for(int i=0;i<n;i++)
int dist[maxn][maxn];
bool vis[maxn];
vector<int> v[maxn];
int dep[maxn];
deque<int> vv[maxn];
void dfs(int u){
	vv[dep[u]].pb(u);
	for(int x:v[u]){
		dep[x]=dep[u]+1;
		dfs(x);
	}
}
int get(int a,int b){
	int d=0;
	while(a!=b){
		if(dep[a]>dep[b]){
			a=(a-1)/2;
		}
		else b=(b-1)/2;
		++d;
	}
	return d;
}
vector<int> createFunTour(int n, int q) {
	if(n>500){
		REP1(i,n-1){
			v[(i-1)/2].pb(i);
		}
		dfs(0);
		int st=n-1;
		vector<int> ans;
		REP(i,n){
			ans.pb(st);
			int mx=0,p=0;
			for(int j=19;j>=0;j--){
				if(sz(vv[j])){
					int a=vv[j][0];
					if(get(st,a)>mx){
						mx=get(st,a);
						p=a;
					}
					a=vv[j].back();
					if(get(st,a)>mx){
						mx=get(st,a);
						p=a;
					}
				}
			}
			st=p;
		}
	}
	int st=0,mx=0;
	REP(i,n){
		REP(j,i){
			dist[i][j]=hoursRequired(i,j);
			if(dist[i][j]>mx){
				mx=dist[i][j];
				st=i;
			}
		}
	}
	REP(i,n){
		REP(j,n){
			if(!dist[i][j]) dist[i][j]=dist[j][i];
		}
	}
	vector<int> ans;
	REP(asd,n){
		ans.push_back(st);
		vis[st]=1;
		int mx=0,p=0;
		REP(j,n){
			if(!vis[j]){
				if(dist[st][j]>mx){
					mx=dist[st][j];
					p=j;
				}
			}
		}
		st=p;
	}
	return ans;
}

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