Submission #566394

#	Time	Username	Problem	Language	Result	Execution time	Memory
566394		zaneyu	Fun Tour (APIO20_fun)	C++14	21 / 100	212 ms	86320 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=1e5+5;
#define REP(i,n) for(int i=0;i<n;i++)
int dist[1005][1005];
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) {
	REP1(i,n-1){
		v[(i-1)/2].pb(i);
	}
	dfs(0);
	int st=n-1;
	vector<int> ans;
	REP(i,n){
		if(vv[dep[st]][0]==st) vv[dep[st]].pop_front();
		else vv[dep[st]].pop_back();
		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;
	}
	return ans;
}

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