| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 960118 | tutis | 가장 긴 여행 (IOI23_longesttrip) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "longesttrip.h"
mt19937_64 rng(0);
std::vector<int> longest_trip(int N, int D)
{
vector<int>x,y;
x.push_back(0);
for(int i=1;i<N;i++){
if(are_connected({0}, {i})){
x.push_back(i);
} else{
y.push_back(i);
}
}
if(y.size()>0 && !are_connected(x,y)){
if(x.size()>y.size()){
return x;
} else{
return y;
}
}
if(y.empty()){
vector<int>p;
for(int i=1;i<N;i++){
p.push_back(i);
}
shuffle(p.begin(),p.end());
vector<pair<int,int>>X;
vector<int>Y;
while(!p.empty()){
int x=p.back();
p.pop_back();
bool ok=false;
for(auto it=p.begin();it!=p.end();it++){
if(are_connected({x}, {*it})){
X.push_back({x,*it});
p.erase(it);
ok=true;
break;
}
}
if(!ok){
Y.push_back(x);
}
}
vector<int>ans;
vector<int>p;
ans.push_back({1});
for(int i=2;i<N;i++){
p.push_back(i);
}
while(!p.empty()){
shuffle(p.begin(),p.end(),rng);
bool found=false;
for(int i: p){
if(are_connected({ans.back()}, {i})){
ans.push_back(i);
p.erase(find(p.begin(),p.end(), i));
found=true;
break;
}
}
if(!found){
break;
}
}
ans.push_back(0);
for(int i: p){
ans.push_back(i);
}
return ans;
}
}