제출 #966013

#제출 시각아이디문제언어결과실행 시간메모리
966013Darren0724즐거운 행로 (APIO20_fun)C++17
47 / 100
100 ms21164 KiB
#include "fun.h" #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(),x.end() const int N=200005; int cntid=0; const int INF=1e9; vector<int> sz(N,1),pa(N),ans,dis(N); priority_queue<pair<int,int>> pq[3]; vector<int> createFunTour(int n, int q) { //int H = hoursRequired(0, N - 1); //int A = attractionsBehind(0, N - 1); int c1=0; int need=(n+1)/2; int mn=INF; for(int i=1;i<n;i++){ int t=attractionsBehind(0, 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}); } cntid=r.size(); int last=-1; for(int i=1;i<n;i++){ pair<int,int> p={-1,-1}; for(int j=0;j<cntid;j++){ if(j==last||pq[j].size()==0)continue; p=max(p,make_pair(pq[j].top().first,j)); } last=p.second; if(last==-1&&pq[last].size()==0)while(1){} auto [dis1,idx]=pq[last].top(); pq[last].pop(); ans.push_back(idx); } ans.push_back(c1); /*for(int j:ans){ cout<<j<<' '; } cout<<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...