제출 #966488

#제출 시각아이디문제언어결과실행 시간메모리
966488Darren0724즐거운 행로 (APIO20_fun)C++17
66 / 100
172 ms21704 KiB
#include "fun.h" #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(),x.end() const int N=100005; int cntid=0; const int INF=1e9; vector<int> sz(N,1),pa(N),ans; priority_queue<pair<int,int>> pq[4]; vector<int> createFunTour(int n, int q) { int c1=n-1; int need=n/2+1; int mn=INF; for(int i=0;i<n-1;i++){ int t=attractionsBehind(n-1, i); if(t>=need&&t<mn){ mn=t; c1=i; } } vector<int> r; vector<int> dis0(N,0); for(int i=0;i<n;i++){ dis0[i]=hoursRequired(c1,i); if(dis0[i]==1){ r.push_back(i); } } int rsz=r.size()-1; assert(rsz<=2); vector<vector<int>> dis(rsz,vector<int>(N)); vector<int> vis(N); for(int i=0;i<rsz;i++){ for(int j=0;j<n;j++){ dis[i][j]=hoursRequired(r[i],j); } } for(int i=0;i<n;i++){ if(i==c1)continue; int p=-1; for(int j=0;j<rsz;j++){ if(dis[j][i]<dis0[i]){ p=j;break; } } if(p==-1)p=rsz; pq[p].push({dis0[i],i}); } pq[3].push({0,c1}); cntid=4; int last=-1; int left=n; for(int i=0;i<n;i++){ array<int,3> p={-1,-1,-1}; for(int j=0;j<cntid;j++){ if(j==last||pq[j].size()==0)continue; p=max(p,array<int,3>{pq[j].top().first,(int)pq[j].size(),j}); } pair<int,int> mx={-1,-1}; for(int j=0;j<cntid;j++){ mx=max(mx,{(int)pq[j].size(),j}); } if(left<mx.first*2){ assert(last!=mx.second); p[2]=mx.second; } last=p[2]; assert(last!=-1&&pq[last].size()>0); auto [dis1,idx]=pq[last].top(); pq[last].pop(); ans.push_back(idx); left--; } //ans.push_back(c1); /*for(int j:ans){ cout<<j<<' '; } cout<<endl;*/ return ans; } /* 46 100000 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 0 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 0 31 31 32 31 33 32 34 32 35 33 36 33 37 34 38 34 39 35 40 35 41 36 42 36 43 37 44 37 45 */
#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...