| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 960127 | tutis | Longest Trip (IOI23_longesttrip) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
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>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);
if(!are_connected({ans.back()}, p)){
break;
}
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;
}
}
}
ans.push_back(0);
for(int i: p){
ans.push_back(i);
}
return ans;
}
vector<int>y_;
for(int i=0;i<N;i++){
if(find(y.begin(),y.end(),i)==y.end()){
y_.push_back(i);
}
}
int lo=0;
int hi=y.size()-1;
while(lo<hi){
int m=(lo+hi)/2;
vector<int>vv;
for(int i=lo;i<=m;i++){
vv.push_back(y[i]);
}
if(are_connected(vv, y_)){
hi=m;
} else{
lo=m+1;
}
}
swap(y[y.size()-1], y[lo]);
vector<int>ans=y;
vector<int>p;
for(int i=1;i<N;i++){
if(find(y.begin(),y.end(),i)==y.end()){
p.push_back(i);
}
}
while(!p.empty()){
shuffle(p.begin(),p.end(),rng);
if(!are_connected({ans.back()}, p)){
break;
}
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;
}
}
}
ans.push_back(0);
for(int i: p){
ans.push_back(i);
}
return ans;
}