이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#include "fun.h"
#define X first
#define Y second
#define pb push_back
#define getdis hoursRequired
#define getsz attractionsBehind
const int MAX=100005,mod=1e9+7,M=2000,inf=1e9;
void maxx(int &a,int b){if(b>a) a=b;}
using ii = pair < int ,int > ;
void minn(int &a,int b){if(b<a) a=b;}
void maxp(ii &a,ii b){if(b>a) a=b;}
void minp(ii &a,ii b){if(b<a) a=b;}
bool cp(ii &a,ii b){if(b>a) {a=b;return 1;}else return 0;}
void PL(int &a,int b){a+=b;if(a>=mod) a-=mod;}
///+++++++++++++++++++++++++++++
int a[MAX],sz[4],h[MAX];
bool vs[MAX];
int D[4];
short bel[MAX];
int L[4][MAX];
int getdeep(int v){
ii u = ii (0,0);
int r;
for(int i=1;i<=3;i++) if(i!=v && sz[i]!=0)
if( cp(u,ii(h[L[i][sz[i]]],sz[i])) ) r=i;
return r;
}
bool cmp(int u,int v){
return h[u]<h[v];}
std::vector<int> createFunTour(int n,int Q){
vector < int > vec;
a[0]=n;
int r=0;
for(int i=1;i<n;i++){
a[i]=getsz(0,i);
if(a[i]>n/2 && a[i]<a[r]) {
r=i;
}
}
int cn=0;
for(int i=0;i<n;i++)if(r!=i){
h[i]=getdis(r,i);
if(h[i]==1) D[++cn]=i;
}
vs[r]=1;
for(int i=1,u;i<=cn;i++){
u=D[i];
bel[u]=i;
L[i][1]=u;
vs[u]=1;
sz[i]=getsz(r,u);
///co the toi uu
}
int top[4]={1,1,1,1};
for(int i=0;i<n;i++) if(!vs[i]){
if(getdis(D[1],i)==h[i]-1){
bel[i]=1;
}
else{
if(getdis(D[2],i)==h[i]-1)
bel[i]=2;
else bel[i]=3;
}
L[bel[i]][++top[bel[i]]]=i;
//cout<<i<<' '<<bel[i]<<'\n';
}
for(int i=1;i<=cn;i++){
sort(L[i]+1,L[i]+1+sz[i],cmp);
}
int las=0;
int allsz=n;
bool okk=1;
for(int i=1;i<n && okk;i++){
int z=getdeep(las);
int v=L[z][sz[z]];
vec.pb(v);
sz[z]--;
allsz--;
las=z;
for(int i=1;i<=cn;i++)
if(sz[i]>=allsz/2){
okk=0;break;
}
}
if(!okk && allsz>1){
int sp;
for(int i=1;i<=cn;i++)
if(sz[i]>=allsz/2){
sp=i;break;
}
int z=getdeep(0);
if(z!=las && z!=sp){
int v=L[z][sz[z]];
vec.pb(v);
sz[z]--;
allsz--;
las=z;
}
bool turn=(las!=sp);
//for ( int u:vec) cout<<u<<' ';cout<<'\n';
//cout<<las<<' '<<sp<<'\n';
//cout<<allsz;return vec;
//cout<<sz[sp]<<' '<<allsz<<'\n';
while(allsz>1){
if(turn){
int z=sp;
int v=L[z][sz[z]];
vec.pb(v);
sz[z]--;
allsz--;
las=z;
}
else{
int z=getdeep(sp);
int v=L[z][sz[z]];
vec.pb(v);
sz[z]--;
allsz--;
las=z;
}
turn^=1;
}
}
vec.pb(r);
//cout<<allsz<<'\n';
return vec;
}
컴파일 시 표준 에러 (stderr) 메시지
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:93:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
93 | for(int i=1;i<=cn;i++)
| ^~~
fun.cpp:97:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
97 | int z=getdeep(0);
| ^~~
fun.cpp: In function 'int getdeep(int)':
fun.cpp:30:12: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
30 | return r;
| ^
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:123:22: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
123 | sz[z]--;
| ~~~~~^~
fun.cpp:101:22: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
101 | sz[z]--;
| ~~~~~^~
fun.cpp:28:27: warning: 'sp' may be used uninitialized in this function [-Wmaybe-uninitialized]
28 | for(int i=1;i<=3;i++) if(i!=v && sz[i]!=0)
| ^~
fun.cpp:92:13: note: 'sp' was declared here
92 | int sp;
| ^~
fun.cpp:28:27: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
28 | for(int i=1;i<=3;i++) if(i!=v && sz[i]!=0)
| ^~
fun.cpp:27:9: note: 'r' was declared here
27 | int r;
| ^
# | 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... |