把自己的代码交上去 CE 了,把题解里的代码交上去也全 CE 了,报错信息一样:
No valid executable file was produced by the compiler
/nix/store/js66s0xwjnzg0ggi2lq9bcvlk6x2za13-binutils-2.35.2/bin/ld: /tmp/compiler_mn80se08/lib.o: in function `main':
src:(.text.startup+0x814): undefined reference to `std::__throw_bad_array_new_length()'
collect2: 错误:ld 返回 1
已仔细阅读题目背景,已在程序开头声明了所需函数,实在是搞不明白哪里出问题了。
我的代码:
#include <bits/stdc++.h>
#define inf 1000000007
#define eb emplace_back
using namespace std;
int hoursRequired(int X, int Y);
int attractionsBehind(int X, int Y);
std::vector<int> createFunTour(int N, int Q);
const int N=1e5+5;
int n,k,cent,sz[N],dep[N],son[N],dis[N][3]; vector<int> ans,vec[3];
vector<int> createFunTour(int n,int q){
auto Find_centroid=[&](){
int mn=inf; sz[0]=n;
for (int i=1;i<n;i++) sz[i]=attractionsBehind(0,i);
for (int i=0,val=(n+1)/2;i<n;i++){
if (sz[i]>=val&&sz[i]<mn) mn=sz[i],cent=i;
}
// cout<<"cent: "<<cent<<endl;
};
auto Find_subtrees=[&](){
auto case_2=[&](){
for (int i=0;i<k;i++){
for (int j=0;j<n;j++){
if (j^son[i]) dis[j][i]=hoursRequired(son[i],j);
}
}
for (int i=0;i<n;i++){
if (i^cent) vec[dis[i][1]<dis[i][0]].eb(i);
}
};
auto case_3=[&](){
for (int i=0;i+1<k;i++){
for (int j=0;j<n;j++){
if (j^son[i]) dis[j][i]=hoursRequired(son[i],j);
}
}
for (int i=0;i<n;i++)if(i^cent){
int u=dis[i][0],v=dis[i][1]; dis[i][2]=max(u,v);
if (u==v) vec[2].eb(i),dis[i][2]-=2;
else if (u<v) vec[0].eb(i);
else vec[1].eb(i);
// cout<<"dist: "<<i<<' '<<dis[i][0]<<' '<<dis[i][1]<<' '<<dis[i][2]<<endl;
}
};
for (int i=0;i<n;i++){
if (i^cent) dep[i]=hoursRequired(cent,i);
if (dep[i]==1) son[k++]=i;
}
if (k==2) case_2();
else case_3();
/* cout<<"k: "<<k<<endl;
for (int i=0;i<k;i++){
for (int x:vec[i]) cout<<x<<' ';
cout<<endl;
}*/
};
auto Construct_permutation=[&](){
int lst=inf;
for (int i=0;i<k;i++) sort(vec[i].begin(),vec[i].end(),[&](int x,int y){return dis[x][i]<dis[y][i];});
// for (int i=0;i<k;i++){
// for (int x:vec[i]) cout<<x<<' ';
// cout<<endl;
// }
for (int turn=1;turn<n;turn++){
auto chk=[&](int id){
int sum=0,mx=0;
for (int i=0;i<k;i++){
int sz=vec[i].size()-(i==id);
if (sz>mx) mx=sz;
sum+=sz;
}
return mx-(sum-mx)<=1;
};
int pos,mx=0;
for (int i=0;i<k;i++)if(!vec[i].empty()){
int d=dis[vec[i].back()][i];
if ((i^lst)&&chk(i)&&d>=mx) mx=d,pos=i;
}
// cout<<"get: "<<pos<<' '<<vec[pos].back()<<' '<<mx<<endl;
ans.eb(vec[pos].back()),vec[pos].pop_back(),lst=pos;
}
ans.eb(cent);
};
if (n<=2) ans.eb(0),ans.eb(1);
else Find_centroid(),Find_subtrees(),Construct_permutation();
return ans;
}