Submission #291058

#TimeUsernameProblemLanguageResultExecution timeMemory
291058TadijaSebezFun Tour (APIO20_fun)C++11
31 / 100
140 ms16112 KiB
#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 sz[N],type[N],dist[N]; vector<pii> v[3]; vector<int> createFunTour(int n,int q){ for(int i=0;i<n;i++)sz[i]=SUB(0,i); int cen=0; for(int i=1;i<n;i++)if(sz[i]*2>=n&&sz[i]<sz[cen])cen=i; type[cen]=-1; for(int i=0,cnt=0;i<n;i++){ dist[i]=DEP(cen,i); if(dist[i]==1&&cnt<2&&sz[i]<sz[cen]){ cnt++; for(int j=0;j<n;j++)if(!type[j]){ if(SUB(j,i)*2>n)type[j]=cnt; } } } for(int i=0;i<n;i++)if(type[i]==0)type[i]=3; for(int i=0;i<n;i++)if(i!=cen)v[type[i]-1].pb({dist[i],i}); if(v[0].size()<v[1].size())swap(v[0],v[1]); if(v[0].size()<v[2].size())swap(v[0],v[2]); if(v[1].size()<v[2].size())swap(v[1],v[2]); bool pu=0; if(v[0].size()>v[1].size()+v[2].size())v[2].pb({0,cen}),pu=1; for(int i=0;i<3;i++)sort(v[i].begin(),v[i].end()); assert(v[0].size()<=v[1].size()+v[2].size()); int las=-1; vector<int> ans; while(max({v[0].size(),v[1].size(),v[2].size()})*2<v[0].size()+v[1].size()+v[2].size()){ int mx=-1,o=-1; for(int i=0;i<3;i++)if(i!=las&&v[i].size()){ if(v[i].back().first>mx)mx=v[i].back().first,o=i; } assert(o!=-1); ans.pb(v[o].back().second); v[o].pop_back(); las=o; } if(v[0].size()<v[1].size())swap(v[0],v[1]); if(v[0].size()<v[2].size())swap(v[0],v[2]); if(v[1].size()<v[2].size())swap(v[1],v[2]); assert(v[0].size()==v[1].size()+v[2].size()); while(v[0].size()){ auto P=[&](int o){ ans.pb(v[o].back().second); v[o].pop_back(); }; P(0); if(v[2].empty())P(1); else if(v[1].empty())P(2); else P(v[1].back().first>v[2].back().first?1:2); } if(!pu)ans.pb(cen); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...