제출 #1202869

#제출 시각아이디문제언어결과실행 시간메모리
1202869ackhavaFun Tour (APIO20_fun)C++20
0 / 100
0 ms324 KiB
#include "fun.h" #pragma GCC optimize "O3,unroll-loops" #pragma GCC target "abm,bmi,bmi2,popcnt,lzcnt,avx,avx2" #include <bits/stdc++.h> #define fi first #define se second #define pb push_back #define all(v) begin(v), end(v) #define REP(i,o,n) for(int i=o;i<n;i++) using namespace std; int centroid(int N){ int ans=0; int vis=N; REP(i,1,N){ int c=attractionsBehind(0, i); if(vis >= c && c >= (N/2))ans=i,vis=c; } return ans; } int mem[100100]; int subtree(vector<int> direct, int center, int i){ if(find(all(direct),i)!=direct.end())return find(all(direct),i)-direct.begin(); REP(x,0,direct.size()-1){ if((hoursRequired(direct[x], i)+1)==mem[i])return x; } return direct.size()-1; } std::vector<int> createFunTour(int N, int Q) { int center = centroid(N); vector<int> direct; vector<deque<pair<int,int>>> vec; REP(i,0,N)mem[i]=hoursRequired(center,i); REP(i,0,N){ if(mem[i]==1)direct.pb(i),vec.emplace_back(); } REP(i,0,N){ if(mem[i])vec[subtree(direct,center,i)].pb({mem[i],i}); } REP(i,0,vec.size()){ sort(all(vec[i])); reverse(all(vec[i])); } vector<int> ans; int lastidx=-1; while(vec.size()){ pair<int,int> mx = {-1,-1}; REP(i,0,vec.size())if(vec[i].size() && i!=lastidx)mx=max(mx,vec[i][0]); REP(i,0,vec.size())if(vec[i].size() && vec[i][0]==mx){lastidx=i;break;} if(mx.fi == -1)break; vec[lastidx].pop_front(); ans.pb(mx.se); int large=-1; int sz=0; REP(i,0,vec.size()){ sz+=vec[i].size(); } REP(i,0,vec.size()){ if(vec[i].size()*2 == sz)large=i; } if(vec.size()==3 && large!=-1){ deque<pair<int,int>> lgx,smx; for(auto i:vec[large])lgx.pb(i); REP(i,0,3)if(i!=large)for(auto j:vec[i])smx.pb(j); sort(all(lgx));reverse(all(lgx)); sort(all(smx));reverse(all(smx)); if(lastidx==large)lastidx=0; else lastidx=1; vec.clear(); vec.pb(lgx); vec.pb(smx); } } ans.pb(center); // cerr<<"! "; // for(auto i:ans)cerr<<i<<" "; // cerr<<endl; 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...