Submission #290859

#	Time	Username	Problem	Language	Result	Execution time	Memory
290859		TadijaSebez	Fun Tour (APIO20_fun)	C++11	0 / 100	10 ms	5376 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>

int SUB(int root,int x){return attractionsBehind(root,x);}
int DEP(int root,int x){return hoursRequired(root,x);}

const int N=100050;
/*int dep[N],sz[N];
int FindCentroid(int n){
	pii mx={0,0};
	for(int i=1;i<n;i++){
		sz[i]=SUB(0,i);
		dep[i]=DEP(0,i);
		if(sz[i]*2>=n)mx=max(mx,{dep[i],i});
	}
	return mx.second;
}
int type[N],dist[N];*/
/*int sub[N],dep[N],side[N];
mt19937 rng(time(0));
vector<int> Solve(vector<int> nodes){
	if(nodes.size()<=1)return nodes;
	int n=nodes.size();
	swap(nodes[0],nodes[rng()%n]);
	int u=nodes[0];
	printf("Solve %i: ",u);for(int i:nodes)printf("%i ",i);printf("\n");
	vector<int> nxt;
	for(int i:nodes){
		if(i==u)dep[i]=0;
		else dep[i]=DEP(u,i);
		if(dep[i]==1)nxt.pb(i);
	}
	int v=nxt[rng()%nxt.size()];
	for(int i:nodes){
		if(i==u)side[i]=1;
		else if(i==v)side[i]=2;
		else side[i]=DEP(i,v)<dep[i]?2:1;
	}
	vector<pii> pts[2];
	for(int i:nodes)pts[side[i]-1].pb({dep[i]-(side[i]==2),i});
	sort(pts[0].rbegin(),pts[0].rend());
	sort(pts[1].rbegin(),pts[1].rend());
	if(pts[0].size()>pts[1].size())swap(pts[0],pts[1]);
	vector<int> ans;
	for(int i=0;i<pts[0].size();i++){
		ans.pb(pts[1][i].second);
		ans.pb(pts[0][i].second);
	}
	vector<int> o;
	for(int i=pts[0].size();i<pts[1].size();i++)o.pb(pts[1][i].second);
	vector<int> sol=Solve(o);
	for(int i:sol)ans.pb(i);
	return ans;
}*/
/*bool was[N];
int n;
int GetMx(int u){
	int mx=0,best=-1;
	for(int i=0;i<n;i++)if(!was[i]){
		int d=DEP(u,i);
		if(d>mx)mx=d,best=i;
	}
	return best;
}
pii mx[N*2];
vector<int> SolveFullBinTree(){
	for(int i=n;i>=1;i--){
		mx[i]=max(mx[i<<1],mx[i<<1|1])+1;
		if(mx[i]==1)mx[i]={1,i};
	}
	for(int u=n;;){
		ans.pb(u-1);
		for(int v=u/2;v;v>>=1){}
	}
}*/
bool Try(priority_queue<pii> tmp[3],vector<int>&ans){
	priority_queue<pii> pq[3];
	for(int i=0;i<3;i++)pq[i]=tmp[i];
	ans.clear();
	if(pq[0].empty())return 0;
	//printf("sz: %i\n",pq[0].size()+pq[1].size()+pq[2].size());
	int u=pq[0].top().second,now=pq[0].top().first,ban=0;
	pq[0].pop();
	ans.pb(u);
	while(1){
		int mx=0,sz=0,o=-1;
		for(int i=0;i<3;i++)if(i!=ban){
			if(pq[i].size()){
				int now=pq[i].top().first;
				if(now>mx||(now==mx&&sz<pq[i].size()))mx=now,sz=pq[i].size(),o=i;
			}
		}
		if(o==-1)break;
		if(mx>now)return 0;
		ban=o;
		ans.pb(pq[o].top().second);
		pq[o].pop();
		now=mx;
	}
	if(pq[ban].size()>1)return 0;
	for(int i=0;i<3;i++)assert(i==ban||pq[i].empty());
	if(pq[ban].size()==1)ans.pb(pq[ban].top().second);
	return 1;
}
int dep[N],dst_cen[N],dst_den[N],side[N],offs[N];
vector<pii> all[N];
vector<int> Solve(int n){
	int cen=0;
	for(int i=1;i<n;i++){
		dep[i]=DEP(0,i);
		if(dep[i]>dep[cen])cen=i;
	}
	int den=0;
	for(int i=0;i<n;i++)if(i!=cen){
		dst_cen[i]=DEP(cen,i);
		if(dst_cen[i]>dst_cen[den])den=i;
	}
	for(int i=0;i<n;i++)if(i!=den)dst_den[i]=DEP(den,i);

	for(int i=0;i<n;i++){
		side[i]=(dst_cen[i]+dst_den[i]-dst_cen[den])/2;
		offs[i]=dst_cen[i]-side[i];
		all[offs[i]].pb({side[i],i});
		assert(side[i]<=dst_cen[den]);
	}
	vector<int> ans;
	for(int i=0;i<=dst_cen[den];i++){
		priority_queue<pii> pq[3];
		for(int j=0;j<i;j++)for(pii p:all[j])pq[0].push({p.first+i-j,p.second});
		for(pii p:all[i])pq[1].push(p);
		for(int j=i+1;j<=dst_cen[den];j++)for(pii p:all[j])pq[2].push({p.first+j-i,p.second});
		if(Try(pq,ans))return ans;
		swap(pq[0],pq[1]);
		if(Try(pq,ans))return ans;
		swap(pq[0],pq[2]);
		if(Try(pq,ans))return ans;
	}
	assert(0);
}
vector<int> createFunTour(int n,int q){
	return Solve(n);
	/*::n=n;
	//if(n>500)return SolveFullBinTree();
	int u=GetMx(0);
	vector<int> ans;
	while(1){
		ans.pb(u);
		was[u]=1;
		u=GetMx(u);
		if(u==-1)break;
	}
	return ans;*/
	/*vector<int> nodes;
	for(int i=0;i<n;i++)nodes.pb(i);
	return Solve(nodes);*/
	/*int cen=FindCentroid(n);
	vector<int> f;
	for(int i=0;i<n;i++){
		dist[i]=DEP(cen,i);
		if(dist[i]==1&&dep[i]==dep[cen]+1){
			f.pb(i);
			type[i]=f.size();
		}
	}
	type[cen]=-1;
	for(int j=0;j<f.size();j++){
		for(int i=0;i<n;i++)if(!type[i]){
			if(SUB(i,f[j])==n-sz[f[j]]+1)type[i]=j+1;
		}
	}
	for(int i=0;i<n;i++)if(!type[i])type[i]=3;
	priority_queue<pii> pq[3];
	for(int i=0;i<n;i++)if(type[i]>0)pq[type[i]-1].push({dist[i],i});
	vector<int> ans;
	int ban=-1;
	while(1){
		int mx=0,sz=0,o=-1;
		for(int i=0;i<3;i++)if(i!=ban){
			if(pq[i].size()){
				int now=pq[i].top().first;
				if(now>mx||(now==mx&&sz<pq[i].size()))mx=now,sz=pq[i].size(),o=i;
			}
		}
		if(o==-1)break;
		ban=o;
		ans.pb(pq[o].top().second);
		pq[o].pop();
	}
	for(int i=0;i<3;i++)while(pq[i].size())ans.pb(pq[i].top().second),pq[i].pop();
	ans.pb(cen);
	return ans;*/
}

Compilation message (stderr)

fun.cpp: In function 'bool Try(std::priority_queue<std::pair<int, int> >*, std::vector<int>&)':
fun.cpp:93:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     if(now>mx||(now==mx&&sz<pq[i].size()))mx=now,sz=pq[i].size(),o=i;
      |                          ~~^~~~~~~~~~~~~

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