제출 #290859

#제출 시각아이디문제언어결과실행 시간메모리
290859TadijaSebez즐거운 행로 (APIO20_fun)C++11
0 / 100
10 ms5376 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 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;*/ }

컴파일 시 표준 에러 (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;
      |                          ~~^~~~~~~~~~~~~
#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...