이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 mn={n,0};
sz[0]=n;
for(int i=1;i<n;i++){
sz[i]=SUB(0,i);
if(sz[i]*2>=n)mn=min(mn,{sz[i],i});
}
return mn.second;
}
int type[N],dist[N];
vector<int> createFunTour(int n,int q){
int cen=FindCentroid(n);
//printf("cen: %i\n",cen);
vector<int> f;
for(int i=0;i<n;i++){
dist[i]=DEP(cen,i);
if(dist[i]==1&&sz[i]<sz[cen]){
f.pb(i);
type[i]=f.size();
}
}
type[cen]=-1;
for(int j=0;j<min(2,(int)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});
//for(int i=0;i<n;i++)printf("%i ",type[i]);printf("\n");
vector<int> ans;
int ban=-1;
//printf("%i %i %i\n",pq[0].size(),pq[1].size(),pq[2].size());
for(int i=1;i<3;i++)if(pq[i].size()>pq[0].size())swap(pq[i],pq[0]);
bool pu=0;
if(pq[0].size()>pq[1].size()+pq[2].size())pq[1].push({0,cen}),pu=1;
//assert(pq[0].size()<=pq[1].size()+pq[2].size());
while(max({pq[0].size(),pq[1].size(),pq[2].size()})*2<pq[0].size()+pq[1].size()+pq[2].size()){
//printf("%i %i %i\n",pq[0].size(),pq[1].size(),pq[2].size());
int mx=-1,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=1;i<3;i++)if(pq[i].size()>pq[0].size())swap(pq[i],pq[0]);
//assert(pq[0].size()==pq[1].size()+pq[2].size());
while(pq[0].size()&&(pq[1].size()+pq[2].size())){
ans.pb(pq[0].top().second);
pq[0].pop();
if(pq[1].empty()||(pq[2].size()&&pq[2].top().first>pq[1].top().first))ans.pb(pq[2].top().second),pq[2].pop();
else ans.pb(pq[1].top().second),pq[1].pop();
}
if(!pu)ans.pb(cen);
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:56: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]
56 | if(now>mx||(now==mx&&sz<pq[i].size()))mx=now,sz=pq[i].size(),o=i;
| ~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |